[백준] 19947 투자의 귀재 배주형 파이썬

문제 링크

www.acmicpc.net/problem/19947

 

푸는 방법

DP를 이용해 해당 년도에 얻을 수 있는 최대값을 구하면 됩니다.

점화식은 다음과 같습니다.

 

dp[i] = max(dp[i-1]*1.05, dp[i-3]*1.2, dp[i-5]*1.35)

만약 10000원과 6년이 주어졌다고 하면,

1년 뒤에 얻을 수 있는 최대 금액은

 

dp[1] = dp[0] *1.05 = 10,000 * 1.05=10,500,

 

2년 뒤에 얻을 수 있는 금액은

 

dp[2] = dp[1] * 1.05 = 10,500  *1.05=11,025,

 

3년 뒤에 얻을 수 있는 금액은

 

dp[3] = max(dp[2] * 1.05 , dp[0] * 1.2) = max(11,025 * 1.05, 10000*1.2) = max (11,576, 12,000) = 12000

 

4년 뒤에 얻을 수 있는 금액은

 

dp[4] = max(dp[3] * 1.05 , dp[1] * 1.2) = max(12000* 1.05, 10500*1.2) = max(12,600, 12,600) = 12600

 

5년 뒤에 얻을 수 있는 금액은

 

dp[5] = max(dp[4] * 1.05, dp[2] * 1.2 , dp[0] * 1.35) = max(12600* 1.05, 11,025*1.2, 10,000* 1.35)
       = max(13,230, 13,230, 13,500 ) = 13500

이런 식으로 진행되서, 최대값은 13500원이 나오게 됩니다. 

 

코드

h, y = map(int, input().split())
dp = [0 for i in range(y+1)]
dp[0]=h

for i in range(1, y+1):
    if i>=5:
        dp[i] = max(dp[i-1]*1.05, dp[i-3]*1.2, dp[i-5]*1.35)
    elif i>=3:
        dp[i] = max(dp[i - 1] * 1.05, dp[i - 3] * 1.2)
    else:
        dp[i] = dp[i - 1] * 1.05
    dp[i] = int(dp[i])

print(int(dp[y]))