[DP] 백준 14501 퇴사 C++

1. 문제

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

14501번: 퇴사

 

2. 풀이

DP를 이용

DP 배열 뒤에서부터 계산(크기 N+1 조심)

#include <iostream>

using namespace std;

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

    int N;
    cin >> N;

    int T[15], P[15], dp[16]; // dp배열 크기 하나 더 크게
    for (int i = 0; i < N; i++) cin >> T[i] >> P[i];

    memset(dp, 0, (N + 1) * sizeof(int));
    
    for (int i = 0; i < N; i++) {
        dp[i + T[i]] = max(dp[i + T[i]], dp[i] + P[i]);
        dp[i + 1] = max(dp[i + 1], dp[i]);
    }

    cout << dp[N];
}

 

DP[i] = max(DP[i+T[i]+P[i], DP[i+1] (i+T[i]<=N) -- i일부터 상담 가능한 경우(당일 상담을 하는 경우와 안하는 경우끼리 최대 비교)

          DP[i+1] (i+T[i]>N) -- i일부터 상담을 못하는 경우

#include <iostream>

using namespace std;

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

    int N;
    cin >> N;
    
    int T[15], P[15], dp[16];
    for (int i = 0; i < N; i++) cin >> T[i] >> P[i];

    memset(dp, 0, (N+1) * sizeof(int));

    for (int i = N - 1; i >= 0; i--) {
        if (i + T[i] <= N) dp[i] = max(dp[i + T[i]] + P[i], dp[i+1]);
        else dp[i] = dp[i+1];
    }

    cout << dp[0];
}