백준 14501 퇴사 c++

 

 

 

처음 작성한 코드는 다음과 같다.

하지만 틀렸다는 결과가 나왔다.

#include <iostream>
using namespace std;

int main(){
    int n;
    cin >> n;
    
    int t[16]; //걸리는 상담시간
    int p[16]; //벌 수 있는 돈
    for(int i=1; i<=n; i++)
        cin >> t[i] >> p[i];
    
    int dp[16] = {0,}; //i날까지 벌 수 있는 돈
    for(int i=1; i<=n; i++){
        if( dp[i]+dp[i+(t[i]-1)-1] > dp[i+(t[i]-1)] )
            dp[i+(t[i]-1)] = dp[i]+dp[i+(t[i]-1)-1];
    }
    
    cout << dp[n];
    return 0;
}

 

 

 

이 문제에서는 for문을 dp 배열의 뒤에서부터 세주는 것이 중요했다.

(지금 이 상담을 할 경우 p더해주기) + (지금 이 상담이 끝나는 날부터 앞으로 또 얻을 수 있는 최대 수익)이 기본 식이다.

뒤에서부터 계산하므로 (지금 이 상담이 끝나는 날부터 앞으로 또 얻을 수 있는 최대 수익) 를 미리 구해놓는 셈인 것이다.

dp문제는 이렇게 점화식을 구한 후 dp배열에 for문을 한번 사용해 계산해주는 것이 중요하다.