[14501] 퇴사(C++)

 

🍃 문제

바로가기

 

🔎 해결 방법

처음에는 앞에서부터 계산을 하려고 했었다. 

예를 들어, dp[n] 을 n일까지 상담을 했을 때 얻을 수 있는 최대 이익이라고 한다면

가능한 모든 경우를 조합해서 그 중 max 값을 찾아서 dp에 저장하려고 했는데

이렇게 하다보니 예외 처리 해줘야 할 것이 너무 많아서 결국 구글링의 도움을 받았다.

첫째날부터 계산을 해도 풀 수 있긴 하지만,

마지막 날 부터 계산을 한다면 코드도 간결하고 훨씬 더 간단하게 답을 도출할 수 있다!

 

만약 위와 같은 표가 주어졌다면,

1. dp[7]

7 + t[7] = 9 > 8 이므로 

7일에 있는 상담은 할 수 없다.

따라서 dp[7] = dp[8] = 0 (dp[n + 1] = 0으로 사전에 초기화 해줘야 함)

 

2. dp[6]

6 + t[6] = 10 > 8 이므로

6일에 있는 상담도 할 수 없다.

따라서 dp[6] = dp[7] = 0

 

3. dp[5]

5 + t[5] = 7 < 8 이므로

5일에 있는 상담은 할 수 있다.

이때 5일에 있는 상담까지 하는게 이득일지, 아니면 그 뒤의 상담만 하는게 이득일지를 계산해주기 위해 비교를 해줘야 하고

dp[5] = max(dp[6], dp[7] + p[5]) = dp[7] + p[5] = 15

 

4. dp[4]

4 + t[4] = 5 < 8 이므로

4일에 있는 상담은 할 수 있다.

dp[4] = max(dp[5], dp[5] + p[4]) = dp[5] + p[4] = 35

 

5. dp[3]

3 + t[3] = 4 < 8 이므로

3일에 있는 상담은 할 수 있다.

dp[3] = max(dp[4], dp[4] + p[3]) = dp[4] + p[3] = 45

 

6. dp[2]

2 + t[2] = 7 < 8 이므로

dp[2] = max(dp[3], dp[7] + p[2]) = dp[3] = 45

 

7. dp[1]

1 + t[1] = 4 < 8 이므로

dp[1] = max(dp[2], dp[4] + dp[1]) = dp[2] = 45

 

최종 답으로 dp[1]을 출력하고 종료!

 

 

💡 내 코드(C++)

Ver.1

// [14501] 퇴사
// https://www.acmicpc.net/problem/14501
// dp, 브루트 포스

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

int main(void)
{
    int n, next, n1, n2;
    vector <int> t;
    vector <int> p;
    int dp[20];
    t.push_back(0), p.push_back(0); // 시작 인덱스를 1로 하기 위해

    cin >> n;
    
    for(int i = 0 ; i < n ; i++) {
        cin >> n1 >> n2;
        t.push_back(n1); p.push_back(n2);
    }

    dp[n + 1] = 0;
    
    for(int i = n ; i > 0 ; i--) {
        next = i + t[i];

        /* 
        n = 7, t[7] = 1 인 경우 7일째의 상담도 할 수 있기 때문에 
        next는 (7 + 1) = 8 까지도 가능
        -> next > n + 1 일 때만 dp[i] = dp[i + 1]
        */
        
        if(next > n + 1) {
            dp[i] = dp[i + 1];
        }
        else {
            dp[i] = max(dp[i + 1], dp[next] + p[i]);
        }
    }

    cout << dp[1] << endl;
}

 

Ver.2

// [14501] 퇴사
// dp[i] = i번째 날부터 마지막날까지의 최대 이익
#include <iostream>
using namespace std;

int n, t[16], p[16], dp[16];

int max(int a, int b)
{
    if(a > b) return a;
    else return b;
}

void getMaxProfit()
{   
    dp[n] = (t[n] == 1) ? p[n] : 0;
    for(int i = n-1; i >= 1; i--) {
        if(i + t[i] <= n + 1) {
            dp[i] = max(dp[i+1], p[i] + dp[i + t[i]]);
        }
        else {
            dp[i] = dp[i+1];
        }
    }
}

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

int main(void)
{
    input();
    getMaxProfit();
    cout << dp[1] << '\n';
}