파이썬 백준 1463번 : 1로 만들기

문제

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

 

풀이

단순히 큰 수로 나눈다고 값을 빠르게 줄일수 있는 것이아니라, 적절한 연산을 섞여야하기때문에 그리디로 해결하기 힘들다.

DP데이블 d에는 각 숫자를 만드는데 최소의 연산횟수가 들어간다. 

1을 빼는 경우는 이전의 연산횟수(이미 최적화 되어있다.)에 1을 더한다

2로 나누어떨어지는 경우, 단순히 1을 뺀 경우와, i로 나눈 경우 중 어느값이 최솟값인지 계산하여 d[i]의 값을 업데이트 한다.

3으로 나누어 떨어지는 경우, 앞선 두 연산(1을 뺌, 2로나눔)의 결과와 3으로 나눈 경우중 최솟값을 계산하여 d[i]의 값을 업데이트 한다. 

import sys

N=int(sys.stdin.readline()) #정수 입력
cnt=0
d=[0]*1000001 #DP테이블 초기화

for i in range(2,N+1):
    d[i]=d[i-1]+1 #1을 빼는 경우
    if i%2==0: #2로 나누어질때, 2로 나누는 경우가 최솟값인지 확인 
        d[i]=min(d[i],d[i//2]+1)
    if i%3==0: #3으로 나누어질때, 3으로 나누는 경우가 최솟값인지 확인 
        d[i]=min(d[i],d[i//3]+1)

print(d[N])