JOI 2010/2011 2번 - 古本屋 (Books) 풀이

 

 

[JOI 2010/2011 2번 - 古本屋 (Books)]

https://www.acmicpc.net/problem/5550

(AC 코드 - https://github.com/MongHwa/Algorithm/blob/main/Baekjoon/Books.cpp)

 

 

책의 장르 $G_i$가 10 이하임을 이용하여 봅시다.

$val[g]$ - 장르가 $g$인 책의 가격이 모인 배열 이라고 할 때, [예제 입력 1]의 배열은 다음과 같습니다.

 

$val[1] = \{14\}$

$val[2] = \{13, 14, 11\}$

$val[3] = \{12, 16\}$

 

이때 장르2의 책 하나를 골라 가격의 최댓값을 만든다면 14를 고르는 게 최적이고, 책 두 개를 고른다면 14와 13을 고르는 것이 최적입니다. 따라서 각 장르에 따라 책을 $k$권 골랐을 때의 최댓값 배열을 $val2[g][k-1]$라 하면. 이 값은 $val[g]$를 정렬한 뒤 누적합을 적용한 것과 같습니다. 즉 $val2[g]$는 다음과 같습니다.

 

$val2[1] = \{14\}$

$val2[2] = \{14, 27, 38\}$

$val2[3] = \{16, 28\}$

 

현재 이 값들은 "같은 장르의 책을 T권 매입할 때, 책 한 권 당 매입 가격이 기준 가격보다 T-1원 높아진다." 규칙을 적용하지 않은 상태입니다. $val2[g][i]$에 대하여 $i*i$를 더해주면 이 규칙을 적용한 값을 구할 수 있습니다. 즉, 수정된 val2 배열은

 

$val2[1] = \{14\}$

$val2[2] = \{14, 29, 44\}$

$val2[3] = \{16, 30\}$

 

 

정해진 한도(여기서는 파려고 하는 책의 수 K) 내에서 어떠한 값(여기서는 총 매입 가격)을 최대화하는 문제이므로 dp를 떠올려볼 수 있습니다. dp식 정의를 다음과 같이 해봅시다.

 

$dp[x]$ - 현재 파려고 하는 책의 수가 $x$권일 때, 총 매입 가격의 최댓값

 

현재 고려하고 있는 책의 장르가 $g$이고, 고려하고 있는 매입 권수가 $k$권이라고 할 때,

$dp[x] = max(dp[x], \;dp[x-k] + val2[g][k-1])$임을 알 수 있습니다.

 

총 시간복잡도는 $O(NK)$입니다.