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

재귀와 동적계획법으로 풀 수 있다.

 

---

 

1. 재귀(브루트포스)

 

 

재귀함수의 변수로는

날짜(인덱스) - int L,

누적상담료 - int psum

으로 설정하였다.

 

현재 날짜를 L이라고 하자.

날짜 L에 상담을 할 것인지 하지 않을 것인지

선택을 해야 한다.

 

1. 날짜 L에 상담하기로 선택했다면,

다음에 선택할 수 있는 날짜는 언제인가?

바로 날짜 L+T[L]부터 상담이 가능할 수 있지 않은가?

그리고 여태껏 누적되어온 상담료 psum에 오늘 선택한 상담료 P[L]을 더한다.

void f(int L, int psum) {
    ...

    f(L+T[L], psum+P[L]);
}

 

다만 조건이 있다.

상담을 진행하는 도중에 휴가날을 맞이할 수는 없는 노릇이다.

그래서 상담할지 선택하기 전에,

다음 상담이 가능한 날짜(L+T[L])가 휴가날 전인지 파악해야 한다.(if문 추가)

void f(int L, int psum) {
    ...
    
    if(L+T[L]<=N+1)
        f(L+T[L], psum+P[L]);
}

 

2. 현재날짜 L의 상담을 선택하지 않고,

바로 다음 날짜부터 고려하는 것이 최선일 수도 있다.

이는 그냥 다음날짜로 넘기면 된다.

void f(int L, int psum) {
    ...
    
    if(L+T[L]<=N+1) f(L+T[L], psum+P[L]);
    f(L+1, psum); //현재날짜 선택안함
}

 

이제 기저조건을 살펴보자.

이전 재귀에서 잡은 다음상담날짜가

지금와서 보니 휴가날(또는 그 이상)이 되었다.

이러면 더 이상 재귀를 진행하지 않고 종료하면 된다.

이 때, 여지껏 상담해와서 번 누적상담료를 res에 저장하고 끝낸다.

void f(int L, int psum) {
    if(L>N) {
        res=max(res, psum);
        return;
    }
    if(L+T[L]<=N+1) f(L+T[L], psum+P[L]);
    f(L+1, psum);
}

 

전체 소스코드는 아래와 같다.

 

정답 소스코드

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

int N;
int T[16], P[16];

int res;

void f(int L, int psum) {
    if(L>N) {
        res=max(res, psum);
        return;
    }
    if(L+T[L]<=N+1) f(L+T[L], psum+P[L]);
    f(L+1, psum);
}

int main() {
    cin>>N;
    for(int i=1; i<=N; i++) cin>>T[i]>>P[i];
    f(1, 0);
    cout<<res<<"\n";
    return 0;
}

 

---

 

2. 동적계획법

 

 

풀이의 핵심은 이렇다.

 

마지막 날부터 첫 날까지 하나씩 고려해볼때,

일을 하는 것이 좋은지 안좋은지 판별해 나가는 것이다.

그러면서 다이나믹 테이블을 작성해 가는 것이다.

 

가장 쉬운 예로,

마지막 날의 상담기간이 1일이라면,

이는 무조건 하는 것이 좋다. 그러나 1일을 초과한다면 못한다.

 

이를 확장하여서,어느 중간날짜 i에 도달하면 그 때는 어떨까?

i+T[i] 날짜는 i 날짜에 상담을 진행하고 나서 다시 상담가능한 날짜이다.

(또는 이 날짜가 휴가날짜여도 된다.)

이 날짜가 휴가날을 초과해서는 안된다.

if(i+T[i]<=N+1) { ... }

 

이제 다이나믹 테이블을 작성할 때다.

작성은 앞서 말했듯, 뒤에서부터 작성하는 것이 쉽다.(for문)

for(int i=N; i>=1; i--) {
    if(i+T[i]<=N+1) { ... }
    ...
}

 

이제 상담을 할 수 있다면,

어느 상담료가 더 큰 지 비교해야 한다. (다이나믹 테이블 DP의 값을 고려한다는 뜻)

이전에 구했던 DP[i + 1]의 값이 큰 지 (거꾸로 진행하니까),

현재날짜에 상담을 진행하고 끝난 날짜 값의 DP 값을 더한 것이 큰 지 말이다.

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

 

만약 상담이 끝난 날짜가 휴가날을 초과한다면,

이 때는 그냥 이전에 구했던 DP값을 불러온다.

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

 

정답 소스코드

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

int DP[20];
int T[20], P[20];

int main() {
    int N;
    cin>>N;
    for(int i=1; i<=N; i++) cin>>T[i]>>P[i];
    for(int i=N; i>=1; i--) {
        if(i+T[i]<=N+1) DP[i]=max(DP[i+1], P[i]+DP[i+T[i]]);
        else DP[i]=DP[i+1];
    }
    cout<<DP[1]<<"\n";
    return 0;
}

 

---

 

사실 동적계획법의 풀이는

티스토리의 jobdong7757님의 풀이를 참고하였다.

필자는 그저 C++로 '번역'만 한 수준이었다.

사고력을 기를 인내를 참지 못하고 풀이를 참고한 것이 부끄럽지만,

한편으로 jobdong7757님에게 감사하기도 하다.

 

문제풀이를 열심히 해야겠다.