[백준 1463 1로 만들기] PYTHON

 

10의 경우 나누기 2를 먼저하면 안되고 -1을 하고 나누기 9를 하는게 가장 빠르다.

그냥 WHILE문으로 조건을 따져 구해볼까 했으나 조건을 찾는게 어려울 것 같아 DP로 풀었다.

 

A=int(input())
dp=[0]*(A+1)
dp[1]=0
for i in range(2,A+1):
    dp[i]=dp[i-1]+1
    if(i%2==0 and dp[i]>dp[i//2]+1):
        dp[i]=dp[i//2]+1
    if(i%3==0 and dp[i]>dp[i//3]+1):
        dp[i]=dp[i//3]+1
print(dp[A])

위처럼 풀면 간단하게 정답을 구할 수 있다.

낮은 배열부터 최소의 경우를 따져 배열에 집어넣고

그러다 보면 결국 마지막 값까지 이를 사용해 구할 수 있다.