[Baekjoon]백준 14501번 퇴사

14501번 퇴사 문제 풀이

문제

• 오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다. 각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다. N = 7인 경우에 다음과 같은 상담 일정표를 보자.

	1일	2일	3일	4일	5일	6일	7일
T(i)	3	5	1	1	2	4	2
P(i)	10	20	10	20	15	40	200

• 상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다. 예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게 된다. 2일에 있는 상담을 하게 되면, 3, 4, 5, 6일에 잡혀있는 상담은 할 수 없다.
  또한, N+1일째에는 회사에 없기 때문에, 6, 7일에 있는 상담을 할 수 없다.
  퇴사 전에 할 수 있는 상담의 최대 이익은 1일, 4일, 5일에 있는 상담을 하는 것이며, 이때의 이익은 10+20+15=45이다.
  상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.

입력

• 첫째 줄에 N (1 ≤ N ≤ 15)이 주어진다.
  둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000)

  출력

• 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.

예제

입력
7
3 10
5 20
1 10
1 20
2 15
4 40
2 200

출력
45

해결방법

변수&함수	내용
num	남은 기간 N
ans	최대 값 저장시킬 변수
a[],b[]	상담기간, 비용
go(index,sum)	날짜인 index와 총 획득 비용 sum을 인자로 받는 함수

• 성공 : N+1번째 날 돈을 받는 경우
• 실패 : N+1이 넘어가는 경우
• 재귀 조건 :
  1. 상담을 하는 경우 : go(index+a[index], sum+b[index])
  2. 상담을 하지 않는 경우 : go(index+1,sum)
• 1일부터 상담이 시작되기 때문에 배열과 함수의 시작을 1로 설정한다.

코드

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

int num;
int ans = 0;
int a[16];
int b[16];

void go(int index, int sum) {
    //index==num날 까지 상담가능, index==num+1이 돈받는날
    if (index == num + 1) {
        if (sum > ans) ans = sum;
        return;
    }
    if (index > num + 1) return;
    go(index + a[index], sum + b[index]);
    go(index +1, sum);
}
int main() {
    cin >> num;
    for (int i = 1; i <= num; i++) {
        cin >> a[i] >> b[i];
    }
    go(1, 0);
    cout << ans << endl;
    return 0;
}