[C++] 백준 14501 문제 해설

14501번: 퇴사

해당 문제에 대해서 여러 풀이가 존재하지만,

이 풀이가 가장 좋아보이기에 주석을 달아 포스팅 해 본다.

 

해당문제에서 명심해야 할 점은 그냥 최고 급여만 출력하면 된다는 점이다.

날짜는 기록할 필요도 없다.

 

힌트는 '거꾸로' 계산하는 것이다.

예로 문제 내용을 보면

7일과 6일은 근무일을 넘어가기에 계산에 포함시켜야될 필요도 없다.

5일 = 15
O

4일 = 20 + 15
O

3일 = 10 + 20 + 15
O

2일 = 20 < (10 + 20 + 15)
X

1일 = (10 + 20 + 15) == (10 + 20 + 15)
O

 

따라서 최고로 나올 수 있는 값은 45 이다.

위 지식을 기반으로 아래 코드를 살펴보자.

 

#include <iostream>

#define MAX 16

int N; // 퇴사일
int Ti[MAX] = {
	0,
}; // 상담일
int Pi[MAX] = {
	0,
}; // 급여
int arr[MAX] = {
	0,
}; // 평가 배열

int max(int a, int b)
{
	return a > b ? a : b;
}

int main()
{
	// 입력으로 퇴사일자 받음.
	std::cin >> N;

	// 입력으로 상담일, 급여를 받음.
	for (int i = 1; i <= N; i++)
	{
		std::cin >> Ti[i] >> Pi[i];
	}

	int deadline;

	for (int i = N; i > 0; i--)
	{
		// deadline 은 현재날짜(i)와 상담일(Ti[i])을 더함.
		// deadline 은 엄밀히 말해, 오늘 근무를 포함시키고 있지 않음.
		// 위 예제에서 i가 7이고, Ti[i] 가 1일경우 8이 됨.
		deadline = i + Ti[i];
		// 하지만 N + 1 을 통해 퇴사일과 보정되므로 상관없음.
		// 더하여 이런 deadline 특성을 이용해 arr 을 더 잘 이용할 수 있음.

		// 만약 deadline 날짜가 퇴사일을 초과하면 상담이 불가함.
		if (deadline > N + 1)
		{
			// 상담이 불가할 시 행하는 구간.
			// 그냥 뒤에서 계산했던 최고치를 현재위치에 재할당함.
			arr[i] = arr[i + 1];
		}
		else
		{
			// 상담이 가능할 시 행하는 구간.
			// arr[i+1] 은 이전에 계산했던 최고치가 삽입되어 있음. 하지만 만약 그 최고치보다.
			// 오늘 받을 수 있는 급여 + 데드라인 후에 받을 수 있는 최고 급여가 더 크다면 해당 값을 max 로 사용.
			// 만약 상담일(i)이 1 이라면 최고치와, 오늘 급여까지 더해 최고치를 갱신함.
			arr[i] = max(arr[i + 1], arr[deadline] + Pi[i]);

			// 결론적으로 arr[1] 값에는 현재로서 받을 수 있는 최고치가 누적되어 있음.
		}
	}

	std::cout << arr[1] << std::endl;
}

예로 아래와 같은 입력값이 주어지면

 

 

최종 arr 은 아래와 같이 설정된다.

따라서 매 진행상황간에 arr[i] 는 항상 최고치일 수 밖에 없으며,

arr[1] 은 전체 프로세스에서 최고값이다.

 

해당 문제는 여러곳에서 응용이 가능하기에, 곱씹어볼만한 필요성이 있다.

정말 군더더기 없이 깔끔하게 작성된 알고리즘이다.