19947번 - 투자의 귀재 배주형
// 이해를 돕기 위한 예시. 실제 동작 X.
0 -> dp[0][i] = dp[0][i-1] * 1.051 -> 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] 로만 비교할 경우 반례가 발생합니다.
dp[i - 1][j] vs. dp[i][j-k]
반례)h: 10017, y: 4 인 경우expected: 12621actual: 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
도움이 됐으면 좋겠습니다.
댓글을 작성하려면 로그인해야 합니다.
morningstar9047 1년 전
// 이해를 돕기 위한 예시. 실제 동작 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
도움이 됐으면 좋겠습니다.