백준 알고리즘 14501_퇴사 C

문제

(링크) 14501번: 퇴사 (acmicpc.net)

 

사고과정

문제를 보자마자 '아 DP인가?' 싶었다. 이 것도 dp라고 해야하는지는 잘 모르겠지만 어쨌거나 각 날짜에서 받을 수 있는 상담비를 최댓값으로 갱신하며 탐색하면 될 것 같았다.  

 

내코드

#include <stdio.h>
#include <stdlib.h>



int main() {
	int N,i;
	scanf("%d", &N);
	int** task = (int**)malloc(N * sizeof(int*));
	int* earn = (int*)calloc(N, sizeof(int));
	for (i = 0; i < N; i++) {
		task[i] = (int*)malloc(2 * sizeof(int));
	}
	for (i = 0; i < N; i++) {
		scanf("%d %d", &task[i][0], &task[i][1]);
		if ((N - i) < task[i][0]) {
			task[i][1] = 0;							//하지 못하는 일은 0원으로 추가하지 못하게
		}
		earn[i] = task[i][1];		
	}

	for (i = 0; i < N; i++) {
		int day = i;
		int temp = earn[day];
		day += task[day][0];
		while (day < N) {
			if (temp + task[day][1] > earn[day]) {
				earn[day] = temp + task[day][1];
			}
			day += 1;
		}
	}
	int max = 0;
	for (i = 0; i < N; i++) {
		if (max < earn[i])max = earn[i];
	}

	printf("%d", max);




	for (i = 0; i < N; i++) {
		free(task[i]);
	}
	free(task);
	free(earn);
	return 0;
}

먼저 문제 조건대로 데이터를 입력 받은 뒤, (2중 배열) task에 상담소요기간과 상담비를 저장하였다. 이후 earn배열에 각 날짜에서 받는 상담비를 추가하였다. 이 때, 상담소요기간과 퇴사까지 남은 일자를 비교하여 상담을 진행할 수 없다면 상담비를 0으로 설정해 일을 하지 못하게 만든다.  

이제 첫째 날부터 시작하여 탐색을 시작한다. day변수에 시작날을 저장하고 temp에 시작날에 벌 수 있는 돈을 저장한다. 이후 day에 상담소요기간을 더한다. day가 퇴사하는 날이 될때까지 day에 1을 더하며 earn[day]에 최댓값이 갱신되도록 <temp + 그날 상담비>를 업데이트한다. 이렇게 업데이트 하는 이유는, a번째 날의 상담을 한 뒤, 상담기간이 지난 후의 일은 어느 것이든 할 수 있기 때문이다. 상담비를 최대로 벌기 위해 자체적으로 전략적인 휴무를 가지는 것이 가능하단 뜻이다. 

이 과정을 계속하면 earn[day]에는 각 날짜에 벌 수있는 최대 상담비가 저장되고 earn배열에 저장된 값중 최댓값을 구하면 된다.

 

피드백

솔직히 문제 난이도에 비해 고민시간이 길었던 문제다. 특히 중간에 day+=1을 해가며 문제를 풀어도 중첩되진 않을지 고민을 많이 했다. 다음에 메모리를 줄여보도록 하자