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

문제링크: https://www.acmicpc.net/problem/2073

2073번: 수도배관공사

 

전형적인 dp문제

 

접근방식

 

1. dp를 사용해서 문제를 해결

dp[n] = max(dp[n], cost)

만약 이전 dp값과 합칠 수 있다면  --- temp = min(dp2[j - arr[i][0]], arr[i][1])

dp[j] = max(dp[j], temp); 

 

2. 메모리가 생각보다 크다. 이차원 배열로 풀지 말고 before dp 배열을 하나 만들어서 이전 값과 비교해주면서 진행!

 

문제풀이 

1. dp!

2. 두 점화식을 구현!

 

아래는 정답코드입니다.

#include <iostream>
#include <algorithm>
using namespace std;

int d, p;

int dp[100001];
int dp2[100001];
int arr[351][2];
int temp = 0;
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> d >> p;
	for (int i = 1; i <= p; i++) 
		cin >> arr[i][0] >> arr[i][1];
	
	for (int i = 1; i <= p; i++) {
		for (int j = 1; j <= d; j++) {
			if (j == arr[i][0])
				dp[j] = max(dp[j], arr[i][1]);
			
			if (j > arr[i][0]) {
				if (dp2[j - arr[i][0]] != 0) {
					temp = min(dp2[j - arr[i][0]], arr[i][1]);
					dp[j] = max(dp[j], temp);
				}
			}
		}

		for (int j = 1; j <= d; j++) {
			//cout << dp[j] << ' ';
			dp2[j] = dp[j];
		}
		//cout << endl;
	}

	cout << dp[d] << endl;
	return 0;
}