문제 링크
https://www.acmicpc.net/problem/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일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다.
상담을 하는데 필요한 기간은 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)
💻출력
첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.
✍코드
#include<stdio.h>
#include<iostream>
using namespace std;
void rec(int day, int m);
// global variables
int check[20] = { 0, };
int T[15];
int P[15];
int N;
int money=0, temp=0, mark=0;
// main function
int main(void) {
cin >> N;
for (int i = 0; i < N; i++) cin >> T[i] >> P[i];
rec(0,0);
cout << money;
}
// recusive function
void rec(int day, int m) {
if (check[N] == 1) {
if (temp - P[m] > money) money = temp-P[m];
return;
}
if (check[N - 1] == 1) {
if (temp > money) money = temp;
return;
}
for (int i = day; i < N; i++) {
if (check[i] == 0) {
for (int j = 0; j < T[i]; j++) check[i + j] = 1;
temp += P[i];
mark = i;
rec(i+T[i],mark);
for (int j = 0; j < T[i]; j++) check[i + j] = 0;
temp -= P[i];
}
}
}📝접근 원리 및 코드 구현
접근 원리
이 문제는 앞서 풀어보았던 암호만들기와 비슷한 원리로 접근하였다. 바로 조합(Combination)을 활용하는 방법이다.
코드 구현
// global variables int check[20] = { 0, }; int T[15]; int P[15]; int N; int money=0, temp=0, mark=0;이 부분은 전역 변수를 선언한 부분이다.
check[20] 배열은 재귀함수 속에서 몇일까지 일을 진행했는지를 표시하기 위해 만들어졌으며, N의 최댓값과 T의 최댓값이 각각 15와 5이므로, 아무리 커도 20일을 넘지 않는다. 따라서 인덱싱을 20으로 해주었다.
T[15]와 P[15] 배열, N은 각각 입력되는 T값과 P값, N값을 저장하기 위해 선언해주었다.
money는 최종적으로 출력될 최대 이익을 저장하기 위해, temp는 여러가지 경우의 수의 이익을 저장하기 위해, 그리고 mark는 밑에서도 설명하겠지만, 가장 최근에 더한 이익이 몇일날의 이익인지 표기하기 위해 선언해주었다. 각각 재귀함수가 끝나도 유지되어야 하므로 전역 변수로 선언해주었다.
// main function int main(void) { cin >> N; for (int i = 0; i < N; i++) cin >> T[i] >> P[i]; rec(0,0); cout << money; }메인 함수는 매우 단순하다. N과 T, P를 입력받고, 재귀함수를 호출, 그리고 최대 이익을 출력해주는 역할을 한다.
// recusive function void rec(int day, int m) { // 조건문 if (check[N] == 1) { if (temp - P[m] > money) money = temp-P[m]; return; } if (check[N - 1] == 1) { if (temp > money) money = temp; return; } //반복문 for (int i = day; i < N; i++) { if (check[i] == 0) { for (int j = 0; j < T[i]; j++) check[i + j] = 1; temp += P[i]; mark = i; rec(i+T[i],mark); for (int j = 0; j < T[i]; j++) check[i + j] = 0; temp -= P[i]; } } }이 부분이 이번 문제의 핵심인 재귀 함수 부분이다. 매개변수는 day는 해당 시기의 몇일날까지 진행되었는지 표기하기 위한 변수이며, m은 가장 최근에 더한 이익이 몇일날의 이익인지 표기하기 위한 변수이다. 코드 진행의 특성상 아래의 반복문을 먼저 살펴보자.
day부터 시작해 N-1까지 반복한다. 우선 바로 나오는 조건문을 통해 일이 몇일날까지 진행되는지 표시해준다. 만약 check[i]에 0이 들어있다면, i+1번째 날의 일을 진행할 수 있으므로, T[i]만큼 check[]배열에 1을 표기해준다. 이렇게 되면 i+1번째 날의 일을 진행한 것이므로, temp변수에 P[i]값을 저장해주고, 현재 i값을 mark에 저장해준다. 그 후 재귀함수에 i+T[i]와 mark를 넣어 실행시켜준다. 그렇게 되면, i+T[i]번째 날의 일을 앞선 상황과 똑같이 진행할 수 있다. 이런식으로 반복한 후, 만약 i가 N보다 작아진다면 더 이상 반복할 수 없으므로 반복문에서 빠져나오고 직전 재귀함수로 리턴하게 된다. 그 후 돌아간 재귀함수에서 바꾼 check[]배열과 temp값을 원래대로 돌려주게 된다.
앞선 반복문을 통해 반복되는 상황을 끝내주는 것이 위의 조건문이다. 첫번째 조건문은 check[N]에 1이 들어있을 경우 실행된다. 즉, 해당 경우의 수가 일할 수 있는 일을 초과했을 경우를 의미한다. 따라서 temp-P[m]값을 통해 가장 직전에 더한 이익을 빼준 값을 money와 비교하고 리턴하게 된다. temp에 P[m]값을 빼주는 이유는 해당 temp에 일할 수 없는 날짜의 이익까지 더해져 있기 때문이다. 두번째 조건문은 앞선 조건문을 통해 check[N]이 0이라는 사실을 가지고, check[N-1]에 1이 들어있을 경우 실행된다. 즉 정확하게 일할 수 있는 일을 맞추었을 경우를 의미한다. 따라서 temp와 money를 비교하고 리턴하게 된다.
이렇게 조건문과 반복문이 들어있는 재귀함수를 실행시키면 가능한 모든 경우의 수를 찾을 수 있으며, 따라서 최종적으로 최대 이익도 찾을 수 있다.
