[C/C++] 백준 14501 퇴사

14501 퇴사

14501번: 퇴사

마지막 날부터 거꾸로 생각하면 풀기 쉬워진다.
DP[i]: n 번째 날부터 i 번째 날까지 일했을 때 얻는 최대 이익.

DP[i]는 두 가지 경우로 나눌 수 있는데, i 번째 날에 잡힌 상담을 하는 경우와 그렇지 않은 경우이다.

 

• i 번째 날에 잡힌 상담을 하지 않는 경우: DP[i] = DP[i + 1]과 같다 할 수 있다.
• i 번째 날에 잡힌 상담을 하는 경우: DP[i] = DP[ i + (i 번째 날에 잡힌 상담 일수)] + (i 번째 날에 잡힌 상담의 금액)

이때 i + (i 번째 잡힌 상담 일수)가 n+1을 넘으면 일을 할 수 없으므로 예외 처리를 해준다.

C

#include <stdio.h>
#define MAX(a, b) (((a) > (b)) ? (a) : (b))

int DP[18];
int t[18];
int p[18];

int main() {
    int n, prev;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d %d", &t[i], &p[i]);

    for (int i = n; i > 0; i--) {
        prev = i + t[i];
        if (prev > n + 1) DP[i] = DP[i + 1];
        else DP[i] = MAX(DP[i + 1], DP[prev] + p[i]);
    }
    printf("%d\n", DP[1]);

    return 0;
}

 

t[i]는 i번째 날에 잡힌 상담의 기간, p[i]는 i번째 날에 잡힌 상담의 금액이다.

C++

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

int DP[18];
vector<pair<int, int>> tp(18);

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, prev;
    cin >> n;
    for(int i=1; i<=n; i++)
        cin >> tp[i].first >> tp[i].second;

    for(int i=n; i>0; i--){
        prev = i + tp[i].first;
        if( prev > n+1) DP[i] = DP[i+1];
        else DP[i] = max(DP[i+1], DP[prev] + tp[i].second);
    }
    cout << DP[1] << '\n';

    return 0;
}

 

C++에서는 pair자료형의 vector를 사용하였다.

tp[i].first는 위 C 코드에서의 t[i]와 같고, tp[i].second는 p[i]와 같다.