[C] 백준 14501번 퇴사

 

안녕하세요 (╹ڡ╹ ) ...

오늘의 두번째 문제입니다!

이번 문제 역시 삼성 SW 역량 테스트 기출문제에서 가져왔습니다.

 

백준 14501번

www.acmicpc.net/problem/14501

14501번: 퇴사

.

문제에서 N 값의 입력 범위를 살펴보면, 1 ≤ N ≤ 15인 것을 알 수 있습니다.

범위가 그렇게 크지 않은 것을 보니 제가 좋아하는 재귀함수로 쉽게 풀 수 있는 문제인 것 같습니다!

따라서 저는 재귀 함수로 간단하게 코드를 작성하였습니다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int n;
int t[15], p[15];
int profit, max = 0;

// index -> next
// profit -> now
void consult(int index, int profit) {

	// printf("(%d, %d) ", index, profit);

	if (index > n) {
		// printf("\n");
		return;
	}
	if (profit > max)
		max = profit;

	if (index == n) {
		// printf("\n");
		return;
	}

	// choose O
	consult(index + t[index], profit + p[index]);
	// choose X
	consult(index + 1, profit);
    
}

int main() {

	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%d%d", &t[i], &p[i]);

	consult(0, 0);

	printf("%d", max);

	return 0;
    
}

 

consult 함수는 index와 profit이라는 2개의 인자를 가집니다.

index는 다음번에 살펴볼 날을 뜻하고, profit은 현재까지의 금액을 의미합니다.

즉, 우리는 최대 profit을 가질 경우를 찾아내면 됩니다.

 

그리고 재귀함수인 consult 함수는 크게 2개의 흐름으로 진행됩니다.

1. index에 해당하는 날에 일을 한다 →  금액을 받는다 → 상담이 완료된 이후의 날을 판단한다. (1, 2번 과정 다시 반복)

2. index에 해당하는 날에 일을 하지 않는다 →  금액을 받지 않는다 →  다음 날을 판단한다 (1, 2번 과정 다시 반복)

 

해당 재귀함수의 종료는 index를 기준으로 판단할 수 있습니다.

index는 다음번에 살펴볼 날을 의미하기 때문에 index가 n 이상일 때는 판단해야 할 부분이 2가지 있습니다.

1. index가 n일 때 → 지금 판단할 날이 마지막 날 + 1 → 딱 마지막 날까지 채워서 일을 했음을 의미 → (조건 만족)

2. index가 n 보다 클 때 → 지금 판단할 날이 마지막 날 + 1 + a → 마지막 날을 넘겨서까지 일을 해야함을 의미 (조건 불만족)

따라서 profit의 최대를 구하는 조건은 1번과 2번 사이에 존재해야 함을 알 수 있습니다.

(2번의 경우에서는 현재의 profit이 최댓값인지를 판단해서는 안됨)

 

저는 마지막 재귀 함수의 종료 조건에서 잠깐 고민을 했었는데,

이 부분은 주석으로 처리해놓은 디버깅용 코드의 주석을 해제하고 직접 출력을 해보면 쉽게 수정할 수 있습니다!

.

역시 재귀함수 문제는 언제 풀어도 재밌는 것 같습니다.

편식이 심해지는 중