시간 다이나믹 프로그래밍 기본 문제 틀리기 쉬운 점 복기하면서 재활

1. 문제

 

19947번: 투자의 귀재 배주형 (acmicpc.net)

19947번: 투자의 귀재 배주형

 

2. 풀이

 

아주 기본적인? 다이나믹 프로그래밍..

 

근데 어떻게 하는건지 잠깐 기억이 안났었다는게 함정

 

dp를 길이가 y+1인 배열 [0]*(y+1) 초기화할테고

 

dp[0] = h여서.. y년 후의 금액이 dp[y]라고 해서..

 

1년,3년,5년 투자 방식중 최댓값을 골라 dp에 저장할텐데

 

이거 어떻게 하더라... 잠깐 정적..

 

-----------------------------------------------------------------------------------------

 

그러다가 어렴풋이 dp[i] = max(dp[i-1],dp[i-3]) 이런식으로 했었던게 기억남..

 

3년 6년 9년에는 3년짜리 투자가 가능할테고. >> dp[i] = max(dp[i-1], dp[i-3])

 

5년 10년에는 5년짜리 투자가 가능할거니까... >> dp[i] = max(dp[i-1], dp[i-5])

 

그 이외에는 1년짜리 투자만 가능할테니까... >> dp[i] = dp[i-1]..

 

from sys import stdin

h,y = map(int,stdin.readline().split())

dp = [0]*(y+1)

dp[0] = h

for i in range(1,y+1):
    
    if i % 3 == 0:

        dp[i] = max(dp[i-3]+int(dp[i-3]*0.2),dp[i-1]+int(dp[i-1]*0.05))
    
    elif i % 5 == 0:
        
        dp[i] = max(dp[i-5]+int(dp[i-5]*0.35),dp[i-1]+int(dp[i-1]*0.05))
    
    else:
        
        dp[i] = dp[i-1]+int(dp[i-1]*0.05)

print(dp[y])

 

근데 이러니까 틀리더라..

 

반례를 보니까 4년에는 1년 + 3년 투자가 가능하고

 

6년에는 1년 + 5년 투자가 가능해서.. 3의 배수냐 5의 배수냐를 따지는게 아니라

 

3년 이상부터는 3년짜리 투자가 가능하고

 

5년 이상부터는 5년짜리 투자가 가능하니까..

 

조건문 작성에 주의해서..

 

from sys import stdin

h,y = map(int,stdin.readline().split())

dp = [0]*(y+1)

dp[0] = h

for i in range(1,y+1):
    
    if i >= 5:

        dp[i] = max(dp[i-5]+int(dp[i-5]*0.35),dp[i-3]+int(dp[i-3]*0.2),dp[i-1]+int(dp[i-1]*0.05))
    
    elif i >= 3:
        
        dp[i] = max(dp[i-3]+int(dp[i-3]*0.2),dp[i-1]+int(dp[i-1]*0.05))
    
    else:
        
        dp[i] = dp[i-1]+int(dp[i-1]*0.05)

print(dp[y])

 

아니 근데 이러니까 또 틀리더라고??

 

근데 이제 왜 그러냐 보니까

 

문제에서 소수점 이하는 버려서 받으라니까 

 

dp[i-1] + int(dp[i-1]*0.05)가 아니라.. int(dp[i-1]*1.05)로 하면 정답이더라고?

 

from sys import stdin

h,y = map(int,stdin.readline().split())

dp = [0]*(y+1)

dp[0] = h

for i in range(1,y+1):
    
    if i >= 5:

        dp[i] = max(int(dp[i-5]*1.35),int(dp[i-3]*1.2),int(dp[i-1]*1.05))
    
    elif i >= 3:
        
        dp[i] = max(int(dp[i-3]*1.2),int(dp[i-1]*1.05))
    
    else:
        
        dp[i] = int(dp[i-1]*1.05)

print(dp[y])

 

근데 의문 가질 생각하지 말고.. 그냥 문제 의도가 3번째 코드라고 생각하자.. 검수자도 많아가지고

 

10000부터 100000까지 브루트포스로 두 경우가 다른게 뭐가있는지 보면 10260 5에서 3번째 코드는 13851 나오고 2번째 코드는 13850 나오더라

 

버림을 하고 덧셈을 한거랑.. 정확히 계산을 하고 버림한거랑 오차 누적이 다르다보니 두 값이 언젠가 다르게 될 수 있는거는 직관적이긴한데..

 

아무튼 문제 의도가 3번째 코드였다라고 생각하는게 맞을