[C++] 백준 - 14501 : 퇴사

문제 링크

14501번: 퇴사

 

풀이 )

  각 일차를 확인하면서 최대 이익을 저장하는 배열 dp에 최대이익을 갱신하면서 저장한다.

 

#include <iostream>
using namespace std;

int max(int a, int b) {
        return a >= b ? a : b;
}

int main() {
        int n;
        int dp[16] = { 0, };
        int t[16] = { 0, };
        int p[16] = { 0, };
        cin >> n;
        for (int i = 1; i <= n; i++) {
                cin >> t[i] >> p[i];
        }
        for (int i = 1; i <= n; i++) {
                int temp = 0;
                for (int j = 1; j <= i; j++) {
                        if (i - j >= 0)
                                if(j >= t[i - j + 1]) {
                                        dp[i] = max(temp, dp[i - j] + p[i - j + 1]);
                                        temp = dp[i];
                                }
                }
        }
        cout << dp[n] << endl;

        return 0;
}