[DP #17] (BOJ 15486) 퇴사 2

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

15486번: 퇴사 2

---

접근법

시간을 t[]에, 페이를 p[]에 저장한다.

그리고 dp[i]에 i일차일 때 최대 이익을 저장한다.

Bottom-Up 방식으로 문제를 접근하기 위해서 4일차를 예시로 생각해보자.

 

4일차가 되는 방법은 2가지가 있다.

1. dp[1] + p[i]

2. dp[3] + p[3]

 

따라서, DP[4] = max(DP[1] +p[1], DP[3] + p[3])

이를 다르게 나타내면

DP[1+t[1]] = max(DP[t[1]] + p[1], DP[1+t[1]])

과

DP[3+t[3]] = max(DP[t[3]] + p[3], DP[3+t[3]])

 

for문을 돌면서 각 일차별로 DP를 다음과 같이 나타낼 수 있다.

DP[i+t[i]] = max(DP[i]+p[i] , DP[i+t[i]])

 

이런식으로 하니 예제 4번이 자꾸 80이 나온다.

위 코드는 도착하는 일차의 상담을 무조건 실시해야하기 때문이다.

위 그림처럼 7일차 상담을 패스하고, 8일차 상담을 해야 최대 이익이 다오기 때문에,

이전 값을 저장하고 그 값에 이익을 더해야한다.

 

따라서,

	for (int i = 1; i <= n+1; i++) {
		if (t[i] + i <= n + 1) {
        	maxi = max(maxi, dp[i]); // (X)
			dp[t[i] + i] = max(maxi + p[i], dp[t[i] + i]);
		}
	}

그러나 위 코드처럼 이전 값을 저장하는 maxi를 if문 앞에 넣으면, 틀렸다고 나온다.

그 반례가 다음과 같다.

//(X)
4
1 100
1 1
3 100
1 10
110

//(O)
4
1 100
1 1
3 100
1 10
111

왜냐하면, i=3 일때 if문을 들어가지 않기 때문에 그 전인 i=2일 때의 값이 업데이트가 되지 않는다.

따라서, maxi를 구하는 코드를 if문 밖으로 빼주면 된다.

for (int i = 1; i <= n+1; i++) {
    // if문 안으로가면 틀림
    maxi = max(maxi, dp[i]);
    if (t[i] + i <= n + 1) {
        dp[t[i] + i] = max(maxi + p[i], dp[t[i] + i]);

    }

}

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#define MAX 1500002

using namespace std;

long long t[MAX];
long long p[MAX];

long long dp[MAX];
int n, k;

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

void Print() {
	long long res = 0;
	for (int i = 1; i <= n+1; i++) {
		res = max(dp[i], res);
	}
	cout << res;
}

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

	cin >> n;
	input();
	
	long long maxi = 0;
	for (int i = 1; i <= n+1; i++) {

		maxi = max(maxi, dp[i]);
		
		if (t[i] + i <= n + 1) {
			dp[t[i] + i] = max(maxi + p[i], dp[t[i] + i]);
		}
			
	}
	Print();
}