[C++] 백준 14501 : 퇴사

#include <iostream>
#include <algorithm> // max
using namespace std;

int N;
int T[16]; // 상담 완료 걸리는 기간
int P[16]; // 상담 금액
int dp[16] = {0}; //dp용 배열

int main(int argc, char **argv){
    scanf("%d",&N);
    for(int i=1; i<=N; i++){
        scanf("%d %d",&T[i],&P[i]); // 모두 입력받기
    }

    for(int i=N; i>0; i--){ // 뒤에서부터 탐색, 퇴사일 고려 위해
        int day = i + T[i]; // 처리 완료 날짜 = 현재 날짜 + 걸리는 일
        if(day > N+1){ // 퇴사 일 넘어가는 경우
            dp[i] = dp[i+1]; // 그대로 최대 이익 이월
        } else {
            dp[i] = max(dp[i+1], dp[day] + P[i]); // 현재 최대 이익, 얻을 수 있는 최대 이익 비교
        }
    }

    printf("%d", dp[1]); // 마지막 탐색 값

    return 0;
}

처음에는 하나하나 구하는 브루트포스로 풀었다가 접근 방법이 틀렸음을 알고 인터넷 많이 참고하고 푼 문제. 다음에 다시 풀어봐야겠다... 다이나믹 프로그래밍을 사용한다.

• 퇴사일을 고려하기 위해 뒤에서부터 앞으로 dp를 구한다.

• 퇴사일을 넘어가는 경우 N+1 초과 (N일 1일 걸리는 일을 할 수 있기 때문에 day == N + 1이어도 가능하다 때문에 N+1 초과 시 조건을 준다)

• 퇴사일 넘어가지 않는 경우 지금까지의 최대 이익과 앞으로 얻을 수 있는 이익 비교해서 최대 이익 저장