BOJ [14501] 퇴사

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

1. 분류

다이나믹 프로그래밍

2. 풀이

퇴사하기 전 최대한 뽕을 뽑고 가는 방법을 구하는 문제이다.

한 번의 상담에 소모하는 기간이 있으며 그 동안에는 다른 상담을 진행하지 못한다.

각 상담에는 받을 수 있는 금액이 정해져 있고 완전히 종료해야만 수령할 수 있다.

최대 입력이 15정도로 낮기 때문에 어지간한 방법으로는 시간 제한에서는 상당히 자유로워 보인다.

아래는 문제를 해결하는 데 생각했던 것들이다.

1. 상담을 시작하면 (오늘 + t)일에 p만큼 정산을 받는다.

  - 이번 상담을 진행하는 것이 이익인지를 판단한다.

2. 1일차부터 계산해가며 마지막 날의 최대 금액을 출력한다.

---

3. 소스코드

#include <cstdio>

int dp[25];

int main()
{
	int n;
	scanf("%d", &n);

	for (int i = 0; i < n; i++)
	{
		int t, p;
		scanf("%d %d", &t, &p);

		if (dp[i] > dp[i + 1]) // 내일까지 번 돈이 오늘보다 적으면 오늘 금액을 내일에 넣는다.
			dp[i + 1] = dp[i];

		if (dp[i + t] < dp[i] + p)
			dp[i + t] = dp[i] + p;
	}

	printf("%d\n", dp[n]);
	return 0;
}