백준 14501번 퇴사

- 문제 설명

 

상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.

 

오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.

 

각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.

 

상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.

 

(퇴사일 이후에 일을 끝마치는 경우 금액을 얻을 수 없음)

 

 

- 입력

 

1) 첫째 줄에 N (1 ≤ N ≤ 15)이 주어진다.

 

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

 

 

- 출력

 

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

 

 

* 문제 풀이의 핵심

 

 

1. 브루트포스

 

이 문제는 N 개의 상담 중에서 어떤 날의 상담을 할지 하지 않을지에 대한 모든 경우의 수를 계산하는 문제로 생각할 수 있습니다.

 

 

모든 경우의 수를 재귀로 구현해야 한다.

 

 

2. 알고리즘

 

0) 정답 초기값 설정

 

> 이익은 항상 양수 값이기 때문에 임의의 음수 값으로 정답 초기값을 설정하고 갱신하면 답을 구할 수 있습니다.

 

const int INF = -987654321;

 

 

1) 상담을 진행할 날과 진행하지 않을 날을 재귀로 구현하기

 

* 시작일을 0 일 퇴사일을 N 일을 기준으로 하여 코드를 작성하였습니다.

 

 

- 함수명 : maximum_benefit(int index, int cur, int N)

 

- 파라미터 : index -> 상담일, cur -> 현재까지 계산된 총 이익, N -> 퇴사일

 

 

<1> 정답 : 퇴사일이 N 일이면 알맞게 일을 한 경우기 때문에 이때까지 일한 이익을 리턴하면 됩니다.

 

<2> 불가능 : 퇴사일을 넘겨서 일을 한 만큼의 이익은 고려할 필요가 없기 때문에 절대 정답이 될 수 없는 값을 리턴하면 됩니다.

 

<3> 다음 경우

 

일일이 1일마다 상담을 할지 말지 결정할 필요없이 상담을 완료하는데 걸리는 기간 Ti 일 만큼마다 상담 여부를 결정해도 같은 결과를 얻을 수 있습니다. (상담중인 Ti 기간만큼은 모든 일을 할 수 없기 때문)

 

> 상담을 하는 경우 : Ti 일만큼 상담일을 뒤로 늦추고 Pi 이익만큼 현재 이익에 더하면 됩니다.

 

> 상담을 하지 않는 경우 : 1일 만큼 상담일을 뒤로 늦추면 됩니다.

 

 

// 시작일 : 0 일, 퇴사일 : N 일 기준으로 코드 작성
int maximum_benefit(int index, int cur, int N) {
	int ret = INF;

	// 퇴사일이 N 일 이면 알맞게 그만 둔 경우
	if (index == N) return cur;

	// 퇴사일이 N 보다 크면 초과로 회사를 다닌 것이기 때문에 고려하지 않음
	if (index > N) return INF;

	// index 번째 일에 일을 하는 경우
	ret = max(ret, maximum_benefit(index + T[index], cur + P[index], N));
	
	// index 번째 일에 일을 하지 않는 경우
	ret = max(ret, maximum_benefit(index + 1, cur, N));

	return ret;
}

 

 

* 상담 시작일을 1일로, 퇴사일을 N+1일로 구현하고 싶다면, 입력을 1부터 받고 index를 1부터 시작하면 됩니다.

 

 

 

- 소스코드

 

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<string>

using namespace std;

int T[16];
int P[16];

const int INF = -987654321;

// 시작일 : 0 일, 퇴사일 : N 일 기준으로 코드 작성

int maximum_benefit(int index, int cur, int N) {
	int ret = INF;

	// 퇴사일이 N 일 이면 알맞게 그만 둔 경우
	if (index == N) return cur;

	// 퇴사일이 N 보다 크면 초과로 회사를 다닌 것이기 때문에 고려하지 않음
	if (index > N) return INF;

	// index 번째 일에 일을 하는 경우
	ret = max(ret, maximum_benefit(index + T[index], cur + P[index], N));
	
	// index 번째 일에 일을 하지 않는 경우
	ret = max(ret, maximum_benefit(index + 1, cur, N));

	return ret;
}

int main() {
	int N;
	cin >> N;

	int i;
	for (i = 0; i < N; i++) {
		cin >> T[i];
		cin >> P[i];
	}

	cout << maximum_benefit(0, 0, N) << "\n";
}

 

 

 

- 문제링크 : www.acmicpc.net/problem/14501

14501번: 퇴사

 

 

- 제출한 코드

 

 

 

>  백준 아이디 : canoe726

>  사용언어 : C++

>  에디터 : Visual Studio 2017

>  궁금한점은 댓글로 남겨주세요