[백준] 14501 - 퇴사

www.acmicpc.net/problem/14501

14501번: 퇴사

• 삼성 SW 역량 테스트 문제.
• 최대 이익을 구하는 문제와 유사함.
• 브루트 포스와 다이나믹 프로그래밍을 이용할 수 있음
  • 브루트 포스를 이용할 경우 : O(N^2)
  • 다이나믹 프로그래밍을 이용할 경우 : O(N)
• 풀이
  • 하루마다 입력을 받으면서 다음날과 현재의 최대값을 비교하여 다음날의 값이 현재 보다 작다면 현재의 값으로 변경
  • 상담일이 끝나는 날의 다음날 값(dp[n+time])이 (현재 dp[n] + price) 보다 작다면 dp[n+time]을 치환.
• 느낀점
  • 아직도 dp 문제는 점화식이나 bottom-top, top-bottom 등 여러 가지 방법으로 접근하는 사고가 안된다...
  • 처음에 다이나믹 프로그래밍을 사용할려고 2차원 배열을 만들어 요상하게 계산하고 있었고, 손으로 풀었을 때도 답이 나오지 않아 인터넷 풀이를 보고 이해할려고 노력하였다.
• 코드

#include <iostream>

#define MAX_SIZE 15

int main()
{
	int N = 0;
	std::cin >> N;

	int dp[MAX_SIZE + 1] = { 0, };
	for (int n = 0; n < N; n++)
	{
		int time, price;
		time = price = 0;
		std::cin >> time >> price;

		// 퇴사일 까지 최대값으로 채워주는 조건
		if (dp[n] > dp[n + 1])
			dp[n + 1] = dp[n];

		// 상담이 끝나는 날에 대한 값을 최대값으로 업데이트
		if ( (n+time <= N) && (dp[n + time] < dp[n] + price))
			dp[n + time] = dp[n] + price;
	}
	
	printf("%d\n", dp[N]);

	return 0;
}