[백준 14501번] 퇴사 (조합)

이번 문제는 백준 14501번 퇴사 기출문제입니다. 이 문제를 DP로 풀이할 수 도 있고 조합으로 풀이할 수 도 있습니다. 1~N일 중 어떤 일자를 선택했을 때 최대 수익이 나오는지 판단하는 문제이기 때문에 조합을 여러 번 반복해서 풀이할 수 있습니다.

 

2021.04.16 - [알고리즘/SW역량테스트 기출문제] - [백준 14888번] 연산자 끼워넣기 (순열)

2021.04.08 - [알고리즘/SW역량테스트 기출문제] - [백준 15686번] 치킨배달 (조합)

2021.04.14 - [알고리즘/SW역량테스트 기출문제] - [백준 14889번] 스타트와 링크 (조합)

2021.04.18 - [알고리즘/SW역량테스트 기출문제] - [백준 15683번] 감시 (조합)

2021.04.20 - [알고리즘/SW역량테스트 기출문제] - [백준 14501번] 퇴사 (조합)

 

안녕하세요. 지칸입니다.

오늘 기출문제는 백준 14501번 퇴사 문제입니다. 문제를 읽다 보면 가장 먼저 떠오르는 방법이 조합입니다. 다양한 해법이 존재하겠지만 복수 후보 중 몇 개를 선택해야 하는 문제가 있다면 조합으로 접근하는 것이 직관적일 것으로 생각됩니다.

 

1) 문제 이해

2) 문제 풀이

 

저의 결론) 일반적인 조합 알고리즘 문제에서 정말 살짝 응용한 문제입니다. 조합 기출 목록을 보시면 응용의 단계에 차이가 조금 있지만 대체로 큰 틀은 변하지 않는다는 걸 깨달았을 겁니다.

---

1) 문제 이해

문제 출처 : www.acmicpc.net/problem/14501

 

문제)

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

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

백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.

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

N = 7인 경우에 다음과 같은 상담 일정표를 보자.

	1일	2일	3일	4일	5일	6일	7일
T	3	5	1	1	2	4	2
P	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이다.

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

 

-> 문제 해석

• 1~7일 중 어떤 날을 선택했을 때 최대 수익일까? -> 조합
• 며칠을 선택할까? -> 7C1, 7C2, 7C3, ..., 7C7 전부 체크
• N+1일째에는 회사에 없다. -> 후보군을 줄일 수 있는 요소
• 후보가 결정되었을 때 T값에 따라 겹치는 일이 있는지 체크, 겹치면 스킵

입력)

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

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

 

-> 입력 해석

• MAX_N 15
• MAX_T 5  -> N+1 이후 회사 없다는 조건을 체크할 때 필요
• 3일엔 T 5 이하, 4일엔 T 4 이하, 5일엔 T 3 이하, 6일엔 T 2 이하, 7일엔 T 1 이하

출력)

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

 

-> 출력 해석

• 모든 경우의 수 중 최댓값을 비교하며 유지

---

2) 문제 풀이

기본 세팅을 수행합니다.

2019.04.25 - [알고리즘/SW역량테스트] - (1장-1) 역량 테스트 기본 템플릿 준비

2-1) 초기 세팅

기본적인 input를 받아주는 코드를 작성했습니다. T, P배열의 크기는 MAX_N로 고정됩니다. 사실 vector도 마찬가지로 배열로 써도 상관없습니다. 우리는 N개를 전부 조합의 후보로 가지고 있을 필요가 없다는 걸 문제 해석을 통해 알 수 있었습니다. 예제에서 6일, 7일은 아예 선택할 필요가 없었죠. 이를 위해, check 변수와 maxT를 사용했습니다.

#include <iostream>
#include <vector>
using namespace std;
#define MAX_N 15
#define MAX_T 5
int N;
int T[MAX_N] = { 0, };
int P[MAX_N] = { 0, };
int sol = 0;
vector<int> arr;

int main() {
	cin >> N;
	int maxT = 5;
	int check = N - MAX_T;
	for (int i = 0; i < N; i++) {
		cin >> T[i] >> P[i];
		if (i >= check) {
			if (T[i] > maxT--) {
				continue;
			}
		}
		arr.push_back(i);
	}
    
	// comb	
	cout << sol;
	return 0;
}

T의 최댓값이 5이기 때문에 맨 뒤에서 5개까지만 5,4,3,2,1 이렇게 살펴보면 됩니다. 생각나는 대로 막 짠 거라 더 스마트한 방법이 있을 수 있습니다. 

 

2-2) 조합 구현

여러 번 반복하고 있는 조합 알고리즘 편을 참고하시면 됩니다. 기본과 달라진 점은 comb(n, r)에서 r을 바꿔가며 여러 번 호출한다는 점 말고는 차이점이 없습니다.

2021.04.01 - [알고리즘/SW역량테스트] - (4장-2) 조합(Combination) 알고리즘이란?

vector<int> arr;
vector<int> flag;
vector<int> selectarr;

void comb(int n, int r) {
	if (n == r) {
		for (int i = 0; i < n; i++) {
			flag[i] = 1;
		}
		for (int i = 0; i < arr.size(); i++) {
			if (flag[i] == 1) selectarr.push_back(arr[i]); 
		}
		operation();  
		selectarr.clear(); 
		for (int i = 0; i < n; i++) {
			flag[i] = 0;
		}
		return;
	}
	if (r == 1) {
		for (int i = 0; i < n; i++) {
			flag[i] = 1;
			for (int j = 0; j < arr.size(); j++) {
				if (flag[j] == 1) selectarr.push_back(arr[j]); 
			}
			operation();  
			selectarr.clear(); 
			flag[i] = 0;
		}
		return;
	}
	flag[n - 1] = 1;
	comb(n - 1, r - 1);
	flag[n - 1] = 0;
	comb(n - 1, r);
}

int main() {
	// .. 코드 생략 ..
    
	for (int i = 0; i < arr.size(); i++) {
		flag.push_back(0);
	}
	for (int i = arr.size(); i >= 1 ; i--) {
		comb(arr.size(), i);
	}
	
	cout << sol;
	return 0;
}

main문에 보면 nCr에서 r을 n->1까지 변화를 주면서 comb 함수를 호출하고 있습니다. 이것 말고는 다른 게 없으니 조합 알고리즘 설명은 위 포스팅에서 확인해주세요..

 

2-3) 최대 수익 구현하기

operation이 호출됐다는 건 n개 중 r개만큼 선택했다는 의미입니다. 이 선택한 날짜마다 T값이 존재하기 때문에 일자끼리 겹치는지 체크할 필요가 있습니다. 예를 들어, 1일 T3, 2일 T5 인 경우에는 2일째 여전히 1일의 일이 안 끝난 상태이기 때문에 일이 겹쳐집니다. 이를 위해 over라는 변수를 만들어서 노가다로 오버랩이 발생하는지 체크해 줍니다.

void  operation() {
	//선택한 요일끼리 겹치면 아웃
	int temp;
	int index;
	int over[MAX_N] = { 0, };
	bool overlap = false;
	for (int i = 0; i < selectarr.size() && !overlap; i++) {
		index = selectarr[i];
		temp = T[index];
		for (int j = 0; j < temp && !overlap; j++) {
			if (over[index] == 0 && index < N) {
				over[index++] = 1;
			}
			else
				overlap = true;
		}
	}
	// overlap = true -> skip
	if (overlap) return;

	int total = 0;
	for (int i = 0; i < selectarr.size() && !overlap; i++) {
		total += P[selectarr[i]];
	}
	if (sol < total)
		sol = total;
}

선택한 일자를 전부 체크했을 때 겹치는 게 없다면 선택한 일자의 P를 모두 더해주시면 됩니다. 이 값이 글로벌 sol과 비교하여 최댓값을 유지하면 본 문제는 마무리됩니다.