다이나믹 프로그래밍: 1로 만들기

숫자 x를 입력받는다.

x가 5로 나누어 떨어지는 경우 5로 나눌 수 있고, 3으로 나누어 떨어지는 경우 3으로 나눌 수 있고, 2로 나누어 떨어지는 경우 2로 나눌 수 있으며, 그냥 -1을 할 수도 있다.

이 네가지 연산을 사용하여 x를 1로만드는 최소 연산 횟수를 구하라.

 

 

처음에는 x에서 5로 나눌 수 있으면 5로 나누고, 3으로 나눌수 있으면 3으로 나누고..하는식으로 무조건 큰걸로 나눌 수 있으면 더 빨리 1이 나올거라 생각했는데, 그건 아니었다

 

x=int(input()) #숫자입력

d=[0]*30001 #d[n]은 숫자n이 1이 될 때까지의 연산 횟수를 저장함

#bottom up
for i in range(2,x+1):
    d[i]=d[i-1]+1 #i에서 (-1)연산 한번만 하면 i-1이 되므로, i-1의 연산횟수에 +1한 값으로 설정 해 줌

    if i%2==0: #2로 나누어 떨어질 때
        d[i] = min(d[i],d[i//2]+1) 
        #i에서 -1연산 한번 한 것과, i에서 /2연산 한번 한 것 중 더 낮은 값을 대입
         
    if i%3==0: #3으로 나누어 떨어질 때
        d[i]=min(d[i],d[i//3]+1)
    if i%5==0: #5로 나누어 떨어질 때
        d[i]=min(d[i],d[i//5]+1)

print(d[x])

보텀업 방법을 사용한 다이내믹 프로그래밍.

 

d[n]에 연산 결과를 저장 할 건데, d[n]에는 숫자 n을 1로 만들 때 필요한 최소 연산 횟수를 저장할 것이다.

 

이것을 d[2]부터 d[x]까지 차근차근 계산하고, d[x]를 출력하면 된다. (d[1]은 0임)

 

d[i]에는 d[i-1]+1값을 먼저 넣어준다.

i에서 -1연산을 한 번 하면 i-1이 되므로, i-1의 연산횟수 +1값을 d[i]에 넣는것임.

 

이후에, i가 5로 나누어 떨어지면

앞서 저장해둔 d[i]값과 d[i//5]+1값을 비교한다 (i에서 연산 한번 하면 i//5값이 되니까)

 

이런식으로 3,2로 나누어 떨어지는 경우도 다 계산하여 최솟값을 d[i]에 넣어두고

i가 x까지 모두 반복을 끝내면 d[x]의 값을 출력한다.