[백준] 퇴사 2 15486번 (c++) dp 최댓값으로 갱신하기

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

 

풀이 방법

일반적인 dp 알고리즘인데 여기서 고려해야 할 부분은 경계 값의 처리와, 일을 건너뛰는 경우 최댓값으로 갱신해야 한다는 것이다.

 

dp[i]를 i일 이전까지의 최대로 벌 수 있는 돈이라고 하고 work[i][0], work[i][1]을 각각 소요 시간과, 버는 돈이라고 했을 때

점화식을 dp[i + work[i][0]] = max(dp[i], dp[i + work[i][0]])로만 설정한다면 아래와 같은 문제가 발생한다.

1~3까지 50만 원  5~6까지 20만 원을 벌 수 있을 때 5일에 일을 시작할 때도 50만 원이 최대였다면 50만 원으로 시작해야 하는데, 0원으로 시작한다는 것이다. 그러므로 4일에서 5일에 시작하더라도 50만 원으로 설정해주어야 한다. 

그러므로 아래와 같이 i번째에 왔을 때 지금까지 최댓값과 비교해서 최대값 변수를 초기화 시켜주어야 한다.

    for (int i = 1;i <= N+1;i++) {
        max_money = max(max_money, dp[i]);

 

 

#include <iostream>
#include <vector>
#include <memory.h>
#include <algorithm>

using namespace std;


int N;
int work[1500002][2];
int dp[1500002];

int main() {
    memset(dp, 0, sizeof(dp));
    cin >> N;
    for (int i = 1;i <= N;i++) { //일을 입력 받음
        int a, b;
        cin >> a >> b;
        work[i][0] = a; // 소유되는 시간
        work[i][1] = b; // 받을 돈
    }
    //건너 뛰고 일을 시작해도 된다. 현재까지의 최대를 추가하자!
    int max_money = 0;
    for (int i = 1;i <= N+1;i++) {
        max_money = max(max_money, dp[i]); // 현재까지의 최대 값을 통해 일을 건너 뛴 경우도 포함한다.        
        if (i == N+1) break;
        if (work[i][0] + i  > N + 1) continue; // 일수를 넘어간 경우 다음 경우로 패스
        dp[i + work[i][0]] = max(max_money + work[i][1], dp[i + work[i][0]]); // 일을 끝난 시점에서의 돈 업데이트        
    }
    cout << max_money << endl;
    return 0;
}