[이코다] 다이나믹 프로그래밍

p.217 - 1로만들기 

처음 풀이(오답)

def solution(num):
    cnt=0
    
    def calculate(x):
    
        if x%5==0:
            return x//5
            
        elif x%3==0:
            return x//3
            
        elif x%2==0:
            return x//2
            
        elif x>1:
            return x-1
            
    while num!=1:
        num = calculate(num)
        cnt+=1

solution(26) #5

그리디처럼 푼 처음 풀이

첫 단계에 위와같은 순서로 해야지 가장 작은 연산의 횟수가 나온다고 생각했다.

하지만 위와 같이 하면 2로 먼저 나누게 되고 그러면 답안과 다르게 5라는 답이 나온다.

 

 

이 무제는 다이나믹 프로그래밍이고 그 근거는

1) 부분적인 연산의 합이 답이 된다.

2) 작은 문제로 나눠진다.

 

 

다이나믹 프로그래밍 문제를 처음 접해서 헷갈렸는데,

가령 예시로 x=6이라고 치면

6의 전단계는 가능한 4가지 연산중에 5빼고 다가능하므로

3가지 전 연산들의 연산횟수 중 최소인 값이 f(6)의 값이 된다

-1

//2

//3

//5

 

다른 풀이

def solution():
    x=  int(input())
    d = [0]*30001

    for i in range(2,x+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[x])

solution()

---

p.220 - 개미전사

처음엔 각 개수의 양 사이드만 세는 값들을 더해야 한다고 생각했다.

하지만 다른 놀라운 풀이 방법이 있었다....

 

 

다른 풀이

def solution():
    n = int(input())
    food = list(map(int,input().split()))

    d= [0]*100
    d[0] = food[0]
    d[1] = max(food[0],food[1])
    for i in range(2,n):
        d[i] = max(d[i-1],d[i-2]+food[i])
    return d[n-1]

print(solution())

 

 

다이나믹 프로그래밍은 부분적인 풀이 방법을 점화식으로 계산하는 스킬이 필요함을 깨달았다.

남은 것은 이것이 DP임을 알아차리는 것이다.

 

p.233 - 바닥공사

처음 감이 안잡혀서 고민을 많이 하닥 점화식을 고민했을 때 

 

a[n] = a[n-1] + a[n-2]*3

a[n-1]  은 1개의 경우의 수라 치고 

a[n-2] 는 아래와같이 3경우라고생각했다 .

1X2  2개

2X1  2개

2X2 1개

 

그런데 경우의 수는 2가지였다. 

a[n] = a[n-1] + a[n-2]*2

1X2  2개

2X2 1개

 

정말 아리송해서 계속 생각해보니,

2X1인 경우는 a[n-2]에 속하지 않는 것이었다.

n-2 는 정확히 2개를 남긴 경우에만 속하는 건데 2X1을 하는 순간 n-1에 속하게 되는 것이다..

 

너무 놀라운 알고리즘의 세계다.

많은 문제를 풀어보면서 디테일을 챙기는 연습을 해야겠다는 각오.

 

n = int(input())

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

print(d[n])