[DP] 4문제

출처 - 이것이 코딩테스트다 with Python

1. 1로 만들기

코드

N = int(input())

count=0

d=[0]*(N+1)

#dp[1]=0
for i in range(2,N+1):
    d[i]=d[i-1]+1
    
    if i%2==0:
        d[i] = min(d[i],d[i//2]+1)
        
    if i%3==0:
        d[i] = min(d[i],d[i//3]+1)
    
    if i%5==0:
        d[i] =min(d[i],d[i//5]+1)
    

print(d[N])

숫자i는 i-1에 1을 더한것이므로, d[i] = d[i-1]+1을 해준다. (1을 빼주는 방법 d)
그 후 숫자 i가 2,3,5의 배수인지를 확인하여 최소 연산을 하는 경우의 수를 저장하도록 한다.

2. 개미전사

코드

n = int(input())

stock = list(map(int,input().split()))

dp=[0]*(n+1)

dp[0]=stock[0]
dp[1]=max(stock[0],stock[1])

for i in range(2,n):
    dp[i]=max(dp[i-1],dp[i-2]+stock[i])
    
print(dp[n-1])

i번째에서 선택할 수 있는 최댓값을 구하는 방식으로 했다(bottom-up방식)

3. 바닥 공사

코드

n = int(input())

dp=[0]*(n+1)
dp[1]=1
dp[2]=3

for i in range(3,n+1):
    dp[i] = (dp[i-1]+(2*dp[i-2]))%796796
    
print(dp[n])

i-1번째의 값에 1X2짜리를 붙이는 방법과 i-2번째에 2X1 2개를 붙이거나 2X2짜리 1개를 붙이는 방법이 있다.

이를 점화식으로 표현하면 dp[i] = dp[i-1]+ 2*dp[i-2]가 된다.

이 때, 매 값을 796796으로 나눈 나머지로 저장하라고 했기 때문에 나머지 연산을 해주었다.

4. 효율적인 화폐구성

코드

n,m = map(int,input().split())

coin=[]

for i in range(n):
    tmp = int(input())
    coin.append(tmp)

dp=[10001]*(m+1)

dp[0]=0
for i in range(n):
    for j in range(coin[i],m+1):
        if dp[j-coin[i]]!=10001:
            dp[j] = min(dp[j],dp[j-coin[i]]+1)

if dp[m]==10001:
    print(-1)
    exit()

print(dp[m])

그리디로 풀던 방식에서 화폐의 단위가 바뀌면 푸는 방식이다.