BOJ 14501 : 퇴사 (삼성 SW TEST A형)

삼성 A형 전체 링크

 

www.acmicpc.net/workbook/view/1152 (A형 문제집)

 

www.acmicpc.net/problem/14501

 

 

모든 경우를 다 해봐야 최대 이익을 알 수 있다.

하지만 특정 일에 상담을 한다면, 해당 일 + T[i]일 부터 상담이 가능하다는 조건을 지켜야 한다.

 

모든 경우는 아래와 같다.

1일에 상담 -> 4일, 5일, 6일, 7일 상담 가능.

2일에 상담 -> 7일 상담 가능.

...

7일에 상담 -> 불가능.

 

따라서 DFS를 총 N번 실행한다. (N번째 일을 최초로 시작하는 상담)

/* N일부터 상담 시작, 첫 보수는 0원 부터. */
for (int i = 1; i <= N; i++) DFS(i, 0);

 

input은 날짜가 1일부터 시작하므로 배열을 1부터 채우도록 하자.

for (int i = 1;i <= N;i++) scanf("%d %d", &T[i], &P[i]);

 

DFS 구조는 아래와 같다.

void DFS(int start, int sum)
{
	if(/* 종료 조건 */) return;
    
	for (int i = start + T[start]; i <= N; i++) DFS(i, sum + P[start]);
}

start 날짜가 넘어오면, 다음 가능한 상담일은, start + T[start] ~ N일까지 가능하다.

(위의 예시대로면, 1일에 시작 -> 1 + T[1] = 1 + 3 => 4일 부터 7(N)일)

그러므로 다음 DFS는 지금까지 쌓아온 보수 sum에 현재 상담비용 P[start]를 더해주고 넘기면 된다.

 

이제 종료 조건을 생각해보자.

문제에서 설명했듯이, 6일, 7일은 상담을 할 수가 없다. 6 + T[6]과 7 + T[7]이 7을 넘기 때문이다.

그러나 7일의 T[7]이 1이라면 당일 상담은 가능하므로 이 경우에는 보수를 획득할 수 있다.

void DFS(int start, int sum)
{
	if (start + T[start] > N) /* N + 1을 넘기면 상담 불가 */
	{
    	/* 상담을 시작한 날도 포함되므로, 이 경우에는 보수를 획득할 수 있다. */
		if (start + T[start] == N + 1) sum += P[start];
		
        /* 최대값 갱신 */
		if (ANSWER < sum) ANSWER = sum;

		return;
	}

	for (int i = start + T[start]; i <= N; i++) DFS(i, sum + P[start]);
}

 

만약에 N이 7이고 6일에 T[6]이 2라면 이 경우도 상담 보수는 획득할 수 있다.

즉, 6 + T[6] > 7 이지만, 6 + T[7] == 7 + 1인 경우는 추가로 돈을 더해주어야 한다.

 

최종 코드는 아래를 참고하자.

#include <stdio.h>

#define MAX (20+10)

int N;
int T[MAX];
int P[MAX];

void input()
{
	scanf("%d", &N);
	for (int i = 1;i <= N;i++) scanf("%d %d", &T[i], &P[i]);
}

int ANSWER;
void DFS(int start, int sum)
{
	if (start + T[start] > N)
	{
		if (start + T[start] == N + 1) sum += P[start];

		if (ANSWER < sum) ANSWER = sum;

		return;
	}

	for (int i = start + T[start]; i <= N; i++) DFS(i, sum + P[start]);
}

int main(void)
{
	input();
	
	for (int i = 1; i <= N; i++) DFS(i, 0);

	printf("%d\n", ANSWER);

	return 0;
}

 

실제 시험에서는 tc가 존재하므로, ANSWER = 0으로 초기화 하는 것을 잊지 말자.

int main(void)
{
	int T;
    scanf("%d", &T);
    
    for (int tc = 1; tc <= T; tc++)
    {
        input();
    	
        ANSWER = 0;
        
        ...
        
        printf("#%d %d\n", tc, ANSWER);
    }
   
	return 0;
}

 

이 문제는 N이 커지면 Time out이 나게 된다.

문제 예제 입력 2의 경우 처럼 모든 상담 소요 시간이 1일인 경우, 

눈으로 답을 찾는 것은 쉽지만, 완전 탐색의 경우 매우 비효율적으로 답을 찾게 된다.

 

이 경우는 답을 기억해두는 방법으로 풀 수 있다.

다이나믹 프로그래밍으로 푸는 방법은 여기를 참고하자.

 

A형에서 다이나믹 프로그래밍을 따로 공부해야할 필요는 없다.