백준 1463번: 1로 만들기

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

1463번: 1로 만들기

---

def makeOne(n):
    dp = [0] * (n + 1)

    for i in range(2, n+1):
        dp[i] = dp[i-1] + 1
        if i % 3 == 0:
            dp[i] = min(dp[i], 1 + dp[i//3])
        if i % 2 == 0:
            dp[i] = min(dp[i], 1 + dp[i//2])   
    
    return dp[n]

n = int(input())
print(makeOne(n))

DP는 모든 방법을 일일이 검토하여 최적의 해를 찾아내는 방식이다.

결국 1 빼기, 2 나누기, 3 나누기라는 세 가지 방법을 모두 시도해야 하므로 1 빼기를 먼저 한다.

그리고 2 나누기나 3 나누기를 해보고, min을 이용하여 더 작은 값으로 결정한다.

 

• append보다는 0으로 이루어진 배열을 만든 뒤, 원소를 교체하는 방법으로 하자.
• if, elif가 아니라 둘 다 if문