백준 2073번 - 수도배관공사 (C++)

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

2073번: 수도배관공사

 

배낭문제임은 금방알아챘으나 문제 해결은 하지 못했다.

먼저, 이 문제를 정석적인 배낭문제처럼 2차원 배열로 해결하려하면 메모리 초과가 난다.

2차원 배낭 문제를 1차원으로 바꿔야하는데, 상당히 까다로웠다. 난이도 조절이 필요할 것 같은데.. 

 

논리적으로 언제 파이프를 갱신할 수 있을지 살펴보면, 두개의 파이프가 딱 D와 맞아떨어질 때 갱신이 가능함을 알 수 있다. 그리고 중요한 건 dp[D] 부터 시작해서 Top-down 방식으로 내려가는 것이 현명하다.

 

왜냐하면 3 + 4 로 dp[3] , dp[4] 를 살펴야하는데 Bottom Up 방식으로하면 아직 갱신되지 않았을 수 있다. 

 

그러므로

 

우리는 다음과 같은 점화식을 도출할 수 있다.

 

dp[j] = max(dp[j], min(dp[j - cost], value))

 

 

이 점화식을 해석하면,

먼저 두개의 파이프를 연결가능하다고 하면 둘 중 작은 값을 가져오고, 지금 dp 값과 비교하여 더 큰 값으로 갱신한다.

 

1차원 배낭문제와 2차원 배낭문제의 차이점을 아직 잘 모르겠다.

 

#include <iostream>
#include <vector>

using namespace std;

vector<pair<int, int>> pipe;
int dp[100001];

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

	int D, P;

	cin >> D >> P;

	for (int i = 0; i < P; i++) {
		int a, b;
		cin >> a >> b;
		pipe.push_back({ a, b });
	}
	dp[0] = 123123213;

	for (int i = 0; i < P; i++) {
		int cost = pipe[i].first;
		int value = pipe[i].second;
		for (int j = D; j >= cost; j--) {
			dp[j] = max(dp[j], min(dp[j - cost], value));
		}
	}

	cout << dp[D] << '\n';
}