백준 15486. 퇴사 2

tose33 2022. 7. 2. 17:37

15486번: 퇴사 2

첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000)

www.acmicpc.net

d[i] : i일이 끝나는 시점에 벌수 있는 최대 돈 액수

결론적으로 점화식은 다음과 같다

d[i+day-1] = max(d[i-1] + P[i], d[i+day-1]);

물론 i+day-1이 N을 벗어나는지는 확인해줘야 한다.

점화식이 위와 같이 나온 이유는 d[i]가 i일이 끝나는 시점에 벌수 있는 최대 돈 액수이기 때문에 바로 전날 까지 벌수 있는 최대 돈 + P[i]가 T[i]일 후가 끝나는 시점에 벌수 있는 최대의 돈의 액수가 된다.

또한 매 루프마다 d[i]는 d[i-1], d[i]중 큰 값으로 갱신해 나가야한다.