문제

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

---

풀이

완탐

앞에서부터 차례대로 경우의 수를 따지면서 최대 이익을 갱신하는 식으로 구현했는데, 이 방식은 최적해를 보장하지 않는 거 같다... 그리고 네번째 예제 입력의 답이 도저히 이해되지 않아서 다른 사람 풀이를 참고했다.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
using namespace std;
typedef pair<int, int> pii; 
typedef long long ll;

int N; 
vector<pii> arr;

void input(){
	cin >> N; 

	for(int i = 0; i < N; i++){
		int t, p; 
		cin >> t >> p; 
		arr.push_back({t, p});
	}
}

void solution() {
	int ans = 0;

	// 가능한 모든 경우의 수 중에서 
	// 최대 이익 구하기 
	for(int i = 0; i < N; i++){
		int idx = i, sum = 0;
		
		while(idx < N){
			int t = arr[idx].first; 
			if(idx + t > N) break; 

			sum += arr[idx].second; 
			idx += t; 
		}

		ans = max(ans, sum);
	}

	cout << ans; 
}

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

	input(); 
	solution(); 

	return 0; 
}

DP

참고: https://songsunbi.tistory.com/80

지금과 같이 '최적화 문제'를 풀 때 답이 나오지 않는다면 DP를 떠올려봐야겠다...!!!

DP 문제는 주로 점화식에 따라 작은 문제부터 하나씩 해결해나가면서 상향식으로 최종 해를 구하는 경우가 많다.

그리고 이 문제는 1일부터 생각하는 것보다, 마지막날부터 1일까지 앞으로 가면서 DP 테이블을 채우는 것이 더 쉽다.

• 7일부터 생각해보자. 7일에 잡힌 상담은 2일 걸리기 때문에 퇴사 전에 진행할 수 없다. 따라서 최대 이익은 0이다.
• 6일에도 4일 걸리는 상담이므로, 최대 이익은 0이다.
• 5일에는 2일 걸리는 상담이므로, 5~6일에 진행하여 최대 이익은 15가 된다.
• 4일에는 1일 걸리는 상담이므로, 4일까지의 최대 이익 = 5~6일의 최대 이익 + 4일의 이익 = 35
• 3일에는 1일 걸리는 상담이므로, 3일까지의 최대 이익 = 4~6일의 최대 이익 + 3일의 이익 = 45
• 2일에는 5일 걸리는 상담이므로, 2일에 5일짜리 상담을 받을지, 3~6일까지의 상담 일정을 그대로 가져갈지 최대 이익을 비교해야 한다.
  • 2일에 5일짜리 상담 진행: 7일까지의 최대 이익 + 2일의 이익 = 20
  • 3~6일까지의 최대 이익: 45
  • 따라서, 2일에는 상담을 진행하지 않는 것이 더 이득이다.
• 1일에는 3일 걸리는 상담이므로, 1일에 3일짜리 상담을 받을지, 3~6일까지의 상담 일정을 그대로 가져갈지 최대 이익을 비교해야 한다.
  • 1일에 3일짜리 상담 진행: 4일까지의 최대 이익 + 1일의 이익 = 35 + 10
  • 3~6일까지의 최대 이익: 45
  • 따라서, 두 경우 모두 최대 이익이 동일하다.

이와 같은 과정을 통해 DP 테이블을 채워나가면 다음과 같다. 즉, dp[i]에는 i일까지의 최대 이익을 저장하면 되는 것이다. (마지막날부터 첫째날까지 이동)

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
using namespace std;
typedef pair<int, int> pii; 
typedef long long ll;

int N;
int t[1001];
int p[1001];
int dp[1001];

void input(){
	cin >> N; 

	for(int i = 1; i <= N; i++){
		cin >> t[i] >> p[i];
	}
}

void solution() {
	for(int i = N; i > 0; i--){
		int nextDate = i + t[i];

		// 퇴사 전에 진행할 수 없으면
		if(nextDate > N + 1){
			// 이제까지 구한 최대 이익 그대로 저장 
			dp[i] = dp[i + 1];
		}else{
			// 이제까지 구한 최대 이익  
			// vs 현재 상담을 진행하여 얻을 수 있는 최대 이익
			dp[i] = max(dp[i + 1], dp[nextDate] + p[i]);
		}
	}

	// 최종해 출력 
	cout << dp[1]; 
}

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

	input(); 
	solution(); 

	return 0; 
}

4번째 예제 입력을 다시 보자!!

5 50
4 40
3 30
2 20
1 10
1 10
2 20
3 30
4 40
5 50

이제 이해가 된다... 이처럼 DP를 이용하면, 작은 문제의 해부터 하나씩 해결해나가면서 큰 문제의 해를 구하기 때문에 최종적으로 DP[1]을 통해 우리가 원하는 최적해를 구할 수 있다!