[백준 #1463] 1로 만들기(Python)

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

1463번: 1로 만들기

처음에는 이렇게 쉽지 않을 거란 걸 알면서도.. 

3으로 나누어떨어지면 & 2로 나누어떨어지면 & 둘 다 안되면..으로 풀어봤던 문제다.

해당 힌트에 나와있는 것처럼 10의 경우에는 10 → 9 → 3 → 1 로 3번 만에 만들 수 있지만, 이 방법은 10 → 5 → 4 → 2 → 1 4번을 거쳐야 한다.

 

결국 dp로 전에 있는 결괏값을 활용해야 한다.

n = int(input())

dp = [0] * (n+1)

for i in range(2, n+1):
    dp[i] = dp[i-1] + 1

    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i//2] + 1)
        
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i//3] + 1)

print(dp[n])

우선은 1을 뺄 것이다 가정하여 i보다 1만큼 작은 수의 카운트에서 +1을 한다.

그 후 2로 나누어떨어질 경우 현재(i보다 1만큼 작은 수의 카운트에서 +1을 한 것)와 (i//2 수의 카운트에서 +1을 한 것) 중 작은 값을 적용한다.

3으로 나누어떨어질 경우도 같은 원리다.