[백준 / C언어] 14501번: 퇴사

https://www.acmicpc.net/problem/14501

14501번: 퇴사

 

난이도: solved.ac 실버 3

 

 

실버 3치고 어려웠다...

 

다른 분들은 맨 마지막 날부터 거꾸로 계산하던데 나는 정직하게 첫 날부터 계산했다ㅋ

(거꾸로 계산하는 센스는 dp 문제를 많이 풀어봐야 얻을 수 있나보다...)

 

내 풀이를 예제 입력 1을 통해 설명해보겠다

 

예제 입력 1

7 3 10 5 20 1 10 1 20 2 15 4 40 2 200

 

우선 크기가 N + 1인 1차원 dp 배열을 만든다
(나는 N의 범위를 1000까지로 잘못 봐서 메모리를 적게 하려고 동적할당했는데, 정적할당으로 해도 괜찮을 것 같다)

 

 

일단 1일차.

1일차에 상담을 하면 3일 동안 해서 3일차에 끝난다

그리고 그에 대한 대가로 10을 얻는다
그럼 3일차에 10을 얻는 셈이다
dp[3] = 10를 해주고 그 이후 dp[4], ... 에도 10으로 채운다

(아래의 표에서 idx는 무시하세여..)

 

 

그리고 2일차.
2일차에 상담을 하면 6일차 때 상담이 끝나고 20을 얻을 수 있다
근데 이미 6일차에는 1일차 때 일하고 받은 보상 10이 있다

어떻게 해야할까?

6일차의 보상이 더 높으려면 1일차에 상담을 하지 않고 2일차에 상담하는 게 더 낫다
따라서 dp[6]의 값을 20으로 바꾸고 그 이후 dp[7]도 20으로 바꾼다

 

 

3일차.
3일차에 상담을 하면 3일차 당일에 끝난다
2일차까지 상담을 할지 말지 선택해서 기존에 3일차가 갖고 있던 보상은 10 (1일차에 상담을 해서 얻은 보상)인데0

1일차에 일을 하지 않고 3일차에 일을 한다해도 값이 똑같으므로 PASS 한다

 

 

4일차. 
4일차에 상담하는 것도 당일치기로 4일차에 끝난다
4일차에는 이미 10이라는 값이 있는데, 이는 1일차부터 3일차까지 상담해서 얻은 결과로

4일차와 겹치지 않는다

 

따라서 4일차에 상담을 할 수 있다
따라서 dp[4] = 10(3일차까지 있던 보상) + 20(4일차 상담 보상) = 30 을 해준다
지금까지의 최댓값이므로 나머지 dp[5]부터 dp[7]까지도 30으로 맞춰준다

 

 

5일차.

지겨우니까 여기까지만 설명하겠다

5일차에 상담을 한다면, 이틀짜리니까 6일차에 끝난다
그럼 6일차의 보상은 30(기존 5일차에 있었던 보상) + 15(5일차에 상담해서 얻는 보상) = 45가 된다
따라서 7일차에도 최대로 얻을 수 있는 보상은 dp[7] = 45가 된다

 

 

6일차, 7일차까지 채우면 아래와 같다

N = 7까지라서 6일차, 7일차에 상담을 한다해도 어차피 그 안에 상담을 못 마치니 최대로 얻을 수 있는 이익은 5일차에 결정된다

 

 

지금까지의 과정을 코드로 나타내면 아래와 같다

 

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#define max(a,b) ((a)>(b)?(a):(b))

typedef struct _Consult {
	int T;
	int P;
} Consult;

int main() {
	int N, i, j;
	scanf("%d", &N);
	Consult* consult = (Consult*)calloc(N, sizeof(Consult));
	int* dp = (int*)calloc(N + 1, sizeof(int));

	for (i = 0; i < N; i++)
		scanf("%d %d", &consult[i].T, &consult[i].P);

	int idx, date, max = 0;
	for (i = 1; i <= N; i++) {
		idx = i - 1;
		date = idx + consult[idx].T;
		if (date <= N) {
			dp[date] = max(dp[idx] + consult[idx].P, dp[date]);
			for (j = date + 1; j <= N && dp[date] > dp[j]; j++) {
				dp[j] = dp[date];
			}
			if (dp[date] > max)
				max = dp[date];
		}
	}
	printf("%d", max);
	free(consult);
	free(dp);
	return 0;
}