백준 16138번 수강신청

문제 요약

m개의 과목이 개설된다. 각 과목의 학점과 행복도 $g_i, s_i$가 주어진다. 이 때, $n_{lo}$학점 이상, $n_{hi}$학점 이하로 과목을 듣고자 할 때, 최대 행복도를 찾아야 한다.

m은 최대 20만이고, $n_{lo}, n_{hi}$도 최대 20만이다.

풀이

먼저 각 수업들의 학점별로 행복도의 내림차순으로 정리하자. 그리고 다음과 같은 dp식을 생각해볼 수 있다.
$$
dp(i,j) = \text{i학점까지의 수업들만으로 j학점을 채웠을 때 최대 행복도}
$$
이 dp식의 상태 전이는 다음과 같이 정의할 수 있다.
$$
dp(i,j) = \underset{k<j/i}{max}(dp(i-1, j-ki)+C(i,k))
$$
여기서 $C(i,k)$는 $i$학점의 수업을 $k$개 골랐을 때 얻을 수 있는 최대 행복도이다.

이는 $i$학점짜리 수업들을 내림차순으로 정렬했을 때 앞에서부터 $k$개를 고를 때 최대임이 자명하다. 따라서, 정렬했을 때 누적 합을 구함으로 바로 구할 수 있다.

그리고 $s_{i,k}$를 $i$학점인 수업들을 행복도 순으로 정렬 했을 때 $k$번 째 수업이라고 하자. 그리고 $s_{i,k}$의 누적합을 $p_{i,k}$라고 하자. 어느 순간까지는 $p_{i,k} \le p_{i,k+1}$일 거고, 어느 순간부터는 $p_{i,k} \ge p_{i,k+1}$이 성립할 것이다.

이제 $dp(i,j)$를 최댓값으로 만들어주는 $k$를 $opt_j$라고 하자. 이 $opt_j$는 누적합이 증가하는 동안은 $j < j'(\ge j+ki)$일 때, $opt_j \lt opt_{j'}$가 성립할 것이고, 감소하는 순간부터는 $opt_j = opt_{j'}$가 될 것이다.

따라서, 분할정복 최적화를 적용해서 문제를 푸는것이 가능하다.

다만, 상태전이를 할 때, $i$의 배수를 뺀 값끼리만 상태전이가 가능함에 주의해서 코드를 작성해야 한다.

 

학교 과제로 이 문제가 나왔다고 해서 코드는 지워놓겠습니다.