그냥 하는 노트와 메모장

BOJ 12861 죄수에게 주는 뇌물 [분류 : 다이나믹 프로그래밍] [풀이] [첫번째] 가장 처음에 Q[i]번째 죄수를 석방했다고 해보자. 그러면 1번째 죄수부터 Q[i]-1번째 죄수까지, Q[i]+1번째 죄수부터 P번째 죄수까지 모두 뇌물을 줘야한다. [그 이후의 석방] 이제 죄수를 고를 때 Q명의 죄수 중 i번째를 석방시켰으니, 이젠 구간을 나눠서 봐야한다. 구간 [1, Q[i]-1]에서 Q명의 죄수 중 누굴 석방할 것인지 구간 [Q[i] + 1, P]에서 Q명의 죄수 중 누굴 석방할 것인지 [간단한 dp 아닌가 ?] 그러면 두 구간을 모두 다룰 수 있도록 구간 [l, r]에 대해 부분 문제를 (l, Q[i]- 1) + (Q[i]+1, r)로 두면 되지 않나? 싶은데, 모든 감옥을 인덱스로 담기에는..