// 이해를 돕기 위한 예시. 실제 동작 X.

0 -> dp[0][i] = dp[0][i-1] * 1.05
1 -> dp[1][i] = max(dp[0][i], dp[1][i-3] * 1.20)
2 -> dp[2][i] = max(dp[1][i], dp[2][i-5] * 1.35)

이렇게 dp[i - 1][j] vs. dp[i][j-k] 로만 비교할 경우 반례가 발생합니다.

반례)
h: 10017, y: 4 인 경우
expected: 12621
actual: 12620

expected:
dp[0] = [ 10017, 10517, 11042, 11594, 12173 ]
dp[1] = [ 11017, 10517, 11042, 12020, 12621 ]

=> 12020 * 1.05 = 12621

actual:
dp[0] = [ 10017, 10517, 11042, 11594, 12173 ]
dp[1] = [ 11017, 10517, 11042, 12020, 12620 ]

=> 11517 * 1.20 = 12620.4

도움이 됐으면 좋겠습니다.

댓글을 작성하려면 로그인해야 합니다.