[종만북] 문제: SUSHI
문제
다음과 같은 조건이 주어졌을 때, 얻을 수 있는 최대한의 선호도를 구하시오.
초밥의 종류 $n(1 \leq n \leq 20)$개와 예산 $m(1 \leq m \leq 2^{32} - 1)$와
$price[1…n]$, $preference[1…n]$ 이 주어집니다.
$price(100 \leq price \leq 20000)$이고 100의 배수입니다.
$preference(1 \leq preference \leq 20)$ 이고 자연수 입니다.
서론
지금까지 재귀함수와 DP를 결합해 구현하였습니다.
하지만 DP를 구현하기 위해 공간이 너무 큽니다. 어떻게 할까요?
만약 특수한 상황에서, 반복적 동적 계획법을 쓰면, 공간 복잡도를 단축시킬 수 있습니다.
특수한 경우란? 슬라이딩 윈도(sliding window)가 적용 가능하던가, 행렬 거듭제곱을 이용 가능할 때 입니다.
알고리즘 구상
무한 배낭 문제
무한 배낭 문제는 점화식을 이렇게 나타낼 수 있죠.
\[dp[i] = \max(dp[i], dp[i - weight_j] + value_j) \quad \text{for } weight_j \leq i\]$weight$에 $price$, $value$에 $preference$를 대입하면 맞습니다.
공간이 너무 크다
그런데, 문제는 예산이 $2^{32}-1$라는 것입니다.
재귀적 동적 계획법으로 구현하기 위해서는 int[2^32-1]를 선언해야하는데.. 이건 너무 큰 수죠
반복적 동적 계획법
문제를 다시 보니 $price$가 2만원이 최대입니다. 그렇다면 $dp[i - weight_j]$에서
$i - weight_j$보다 작은 $index$가 연산에 들어가지 않는다는 것입니다. 이를 이용해 코드를 구현 가능합니다.
알고리즘 구현
코드
앞서 설명한 반복적 동적 계획법을 구현한 함수입니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int DP[201];
int sushi() {
int ret = 0;
DP[0] = 0;
for (int budget = 1; budget <= m; budget++) {
int cand = 0;
for (int i = 0; i < n; i++) {
if (budget >= price[i]) {
cand = max(cand, DP[(budget - price[i]) % 201] + preference[i]);
}
DP[budget % 201] = cand;
ret = max(ret, cand);
}
}
return ret;
}
price는 100의 배수이니 $price[1…n]$와 $m$을 /=100하여 공간을 100배 적게 사용 합니다.
아까 말했듯이 각 $price$의 가격은 2만원이 최대이므로 DP[index - 200] 미만 $index$는 접근할 일이 없습니다.
이를 구현하기 위해 DP[]에 접근할 때마다 $index \bmod 201$을 합니다. 그러면 공간을 계속 돌려 쓰겠죠?
이것을 sliding window 기법이라고 합니다.
시간 복잡도는 $O(nm)$입니다.
최종 코드
여기에서 확인하세요!
알고리즘 개선
그리디와 dp를 섞어 풀기
다른 사람은 어떻게 풀었는가 봤는데, 그리디와 DP를 섞어 풀었습니다.
그 중에서 가장 인상적이였던 풀이 코드를 가져와봤습니다.
원리는 대강 이렇습니다.
각 $preference$는 $20$이하 자연수이고, sushi의 개수 $n$은 최대 $20$개입니다.
따라서 중복 없이 얻을 수 있는 최대 선호도 합 $sum$은 $1 \leq sum \leq 400$입니다.
여기서 반복적 동적 계획법을 사용하여, 만족도 k(1 \leq k \leq 400)가 되기 위한 최소 가격을 DP[401]에 얻습니다.
이 과정에서 탐색을 하면서, 가격 대비 선호가 높은 가성비 SUSHI도 미리 계산해 놓습니다.
그 후 0부터 400까지 m에서 빼면서 나머지를 그리디하게 풀면 정답이 나오는 구조입니다.
시간 복잡도를 $O(n)$으로 단축시켜버립니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int dp[401];
int main() {
int cs;
cin >> cs;
while (cs--) {
int ma = 1, mb = 0;
int n, m;
cin >> n >> m;
m /= 100;
for (int i = 1; i < 401; ++i)
dp[i] = 1e9;
while (n--) {
int price, pref;
cin >> price >> pref;
price /= 100;
for (int i = pref; i < 401; ++i)
dp[i] = min(dp[i], dp[i - pref] + price);
if (ma * pref > mb * price) {
ma = price;
mb = pref;
}
}
int r = 0;
for (int i = 0; i < 401; ++i)
if (dp[i] <= m) r = max(r, i + (m - dp[i]) / ma * mb);
cout << r << '\n';
}
return 0;
}
전체 코드는 여기에서 확인할 수 있습니다.