[백준/파이썬] 1463 : 1로 만들기

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

1463번: 1로 만들기

문제 요약 :

• 3으로 나누어 떨어지면 3으로 나눈다.
• 2로 나누어 떨어지면 2로 나눈다.
• 1을 뺀다.

이 세가지 연산을 사용하여 정수X(1이상 10^6이하)를 1로 만드는 최소한의 횟수

 

 

풀이 )

1000000 이하면 dp를 1000001개 만들어줘야하는데 그대로 1000000개만 만들어서 IndexError가 떴었다.

실수를 줄이자..

 

문제에서 주어진 힌트를 보면 10의 경우10 → 9 → 3 → 1 로 3번 만에 만들 수 있다.

dp와 min을 통해 풀 수 있는 문제

dp = [0 for _ in range(1000001)]
dp[2] = 1
dp[3] = 1
N = int(input())

if N > 3 :
    for n in range(4, N+1):
        dp[n] = min(n,dp[n-1]+1)
        if n % 3 == 0:
            dp[n] = min(dp[n],dp[n//3]+1)
        if n % 2 == 0:
            dp[n] = min(dp[n], dp[n//2]+1)
            
print(dp[N])