백준 14501 - 퇴사 (c++)

백준 14501 - 퇴사

문제 링크

생각 및 접근

• 동적 프로그래밍을 통해 n번 날짜에서 가질수 있는 최대 금액을 기록 하려고 했다.

• 상담 일정표에서 맨 앞에 것 부터 탐색한다.

  • 상담이 끝났을 때의 날짜 이후는 그 상담의 보상을 받을 수 있는 날짜들이다. 그러므로, 그 상담이 시작되는 날까지 받을 수 있는 보상 + 그 상담의 보상 이 큰지, 그 상담이 없어도 기존에 가질 수 있는 보상이 더 큰지 비교하면 된다.

      for(int i = 1; i <= n; i++){
          int day = d[i] + i;
          int pay = p[i] + dp[i];
    
          for(int j = day; j <= n + 1; j++){
              dp[j] = max(dp[j], pay);
          }
      }

코드

#include <bits/stdc++.h>
using namespace std;

int n, a, b, d[16], p[16], dp[16];

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

    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a >> b;
        d[i] = a;
        p[i] = b;
    }

    for(int i = 1; i <= n; i++){
        int day = d[i] + i;
        int pay = p[i] + dp[i];

        for(int j = day; j <= n + 1; j++){
            dp[j] = max(dp[j], pay);
        }
    }

    cout << dp[n + 1];
}

채점 결과