[백준] 23061 백남이의 여행 준비 (C++)

23061번: 백남이의 여행 준비

12번 제출해서 겨우 맞춘 문제이다...

최근에 많이 풀었던 유형의 문제라서 풀이는 바로 알아냈다. 그런데도 12번이나 풀었다.

결론부터 말하면 메모리 초과로 매우매우 고생했다. 혹시 비슷한 고민을 하시는 분이 있을까 봐 풀이의 하단에 메모리 초과를 해결한 방법을 기록해두었다! (실제로 채점 현황을 보면 한 페이지에 한 분 꼴로 메모리 초과가 나는 것을 볼 수 있다...ㄷㄷ)

 

 

문제 이해는 어렵지 않다.

물건 N개가 있고 각각 무게 W와 가치 V를 가진다.

용량이 정해진 가방이 M개가 있을 때, 효율성 값이 가장 큰 가방이 무엇인지 출력하는 문제이다.

참고로 효율성 = (가방에 담긴 물건의 가치의 합) / (가방이 견딜 수 있는 최대 무게)이다.

 

---

풀이

전형적인 냅색 DP 문제이다!

M개의 가방 각각 냅색 DP를 돌리지 말고, 가장 무게가 무거운 가방(or K의 최댓값인 1,000,000)을 기준으로 냅색 DP를 돌리면 된다. 가장 무거운 가방을 기준으로 냅색 DP를 돌리면 그보다 가벼운 가방에 담을 수 있는 최대 가치는 이미 구해져 있기 때문이다. 그러고 나서 DP를 통해 구한 값을 이용하여 각 가방의 효율성을 계산한다. 효율성이 가장 큰 가방의 번호가 문제의 정답이다.

 

 

냅색 DP를 구현하는 방법은 2가지가 있다.

첫 번째 방법은 크기 N*K의 2차원 DP 배열을 이용하는 것이다.

두 번째 방법은 크기 K의 1차원 DP 배열을 이용하는 것이다.

(두 가지 방법에 대한 설명은 https://chanhuiseok.github.io/posts/improve-6/ 에 매우 매우 잘 정리되어있다.)

 

이 문제의 메모리 제한은 512MB이기 때문에 첫 번째 방법(int로 선언 시 약 400MB 소모)을 사용하여도 괜찮다. 실제로도 통과한다.

(주의) long long으로 선언 시 약 800MB를 소모하기 때문에 메모리 초과가 난다.

 

그러나, 메모리 제한이 256MB인 냅색 DP문제를 만날 수도 있으니 두 번째 방법을 알아두면 좋다.

아래의 코드도 두 번째 방법을 이용하였다.

 

 

메모리 초과를 해결한 과정은 아래와 같다.

1) 처음 문제를 읽자마자 O(NK) 냅색(knapsack) dp문제인 것을 알아챘고 Top-down으로 dp를 구현했다.

2) 제출했더니 메모리 초과가 났다.

3) 그러다가 신촌 연합 스터디에서 Bottom-Up 방식이 상대적으로 메모리를 작게 먹는다고 했던 것이 기억났다.

4) 혹시 몰라서 Bottom-Up방식으로 다시 짜서 제출했는데 또 메모리 초과가 났다.

5) 그 이후로 결국 이유를 모르겠어서 먼저 푸신 선배에게 질문했는데, 코드를 보자마자 long long이 문제라고 말씀해주셨다.

6) 그래서 dp배열을 long long이 아닌 int로 바꾸니까 바로 맞았다.

 

long long은 8바이트라 N*K인 100*1,000,000을 곱하면 800mb라서 512mb를 넘어간 것이다.

int는 4바이트라 400mb로 통과된다.

(참고로 이 글의 코드는 O(K) dp라서 고작 6000KB로 통과한다.... 선배에게 냅색 DP를 O(N^2)이 아닌 O(N)에 해결하는 방법을 배웠다.)

 

핑계를 좀 대보자면...

int가 4바이트, long long이 8바이트인 것을 모르는 것은 아니었다.

근데, 처음 PS를 배울 때부터 int대신 long long을 써왔었고, 이게 문제가 되었던 적이 없었기 때문에 이것을 전혀 생각해보지 못했다 ㅠㅠ

그래도 이 문제를 통해 메모리도 신경을 쓸 수 있게 되었으니 기분이 좋다.

대회 중에 이런 상황이 벌어졌다면...? 생각만 해도 끔찍하다;;

 

알려주신 선배님께서 메모리를 억 단위로 쓰는 코드는 항상 의심해봐야 한다고 하셨다! 메모...

---

코드

#include <bits/stdc++.h>
#define INF 9876543210
#define endl '\n'
using namespace std;
using ll = long long;

int n, m, ans, maxbag = 0;
int weight[102];
int value[102];
int bag[102];
int dp[1000001];
pair<ll, ll> tmp1;
pair<ll, ll> tmp2;

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> weight[i] >> value[i];
	for (int i = 1; i <= m; i++) {
		cin >> bag[i];
		maxbag = max(bag[i], maxbag);
	}
	for (int i = 1; i <= n; i++) {
		for (int j = maxbag; j >= 0; j--) {
			if (j < weight[i]) break;
			dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
		}
	}
	ans = 1;
	for (int i = 2; i <= m; i++) {
		tmp1 = { bag[ans],dp[bag[ans]] };
		tmp2 = { bag[i],dp[bag[i]] };
		if (tmp1.second * tmp2.first < tmp1.first * tmp2.second) {
			ans = i;
		}
	}
	cout << ans << endl;
	return 0;
}

 

아래의 더보기에 있는 코드는 N*K크기의 dp배열로 해결한 코드이다. (메모리 약 400MB)

#include <bits/stdc++.h>
#define INF 9876543210
#define endl '\n'
using namespace std;
using ll = long long;

int n, m, ans, maxbag = 0;
int weight[102];
int value[102];
int bag[102];
int dp[102][1000001];
pair<ll, ll> tmp1;
pair<ll, ll> tmp2;

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> weight[i] >> value[i];
	for (int i = 1; i <= m; i++) {
		cin >> bag[i];
		maxbag = max(bag[i], maxbag);
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= maxbag; j++) {
			dp[i][j] = max(dp[i][j], dp[i - 1][j]);
			if (j >= weight[i]) {
            	dp[i][j] = max(dp[i][j], dp[i - 1][j - weight[i]] + value[i]);
            }
		}
	}
	ans = 1;
	for (int i = 2; i <= m; i++) {
		tmp1 = { bag[ans],dp[n][bag[ans]] };
		tmp2 = { bag[i],dp[n][bag[i]] };
		if (tmp1.second * tmp2.first < tmp1.first * tmp2.second) {
			ans = i;
		}
	}
	cout << ans << endl;
	return 0;
}