[백준/Python3] 1463번 : 1로 만들기

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

 

문제풀이

import sys

def cnt(N):
    if N <= 1:
        return 0
    if N <= 3:
        return 1
    dp = [0] * (N + 1)
    dp[2] = 1
    dp[3] = 1
    for i in range(4, N + 1):
        if i % 3 == 0:
            if i % 6 == 0:
                dp[i] = min(1 + dp[(i // 3)], 1 + dp[(i // 2)])
            
            else:
                dp[i] = min(1 + dp[(i // 3)], 1 + dp[(i - 1)])
            continue
        elif i % 2 == 0:
            dp[i] = min(1 + dp[(i // 2)], 1 + dp[(i - 1)])
            continue
        else:
            dp[i] = 1 + dp[(i - 1)]
    return dp[N]
N = int(sys.stdin.readline())
print(cnt(N))

 

9를 입력하면 9 -> 3 -> 1 이 될것이다. 기존 값을 3 또는 2로 나누고 count 를 1씩 증가시키는 형태이다. 3의 배수이면 3 나머지 2의 배수이면 2로 나눈 나머지 값이 0임을 판단하여 배수임을 확인한다. 둘다 아닐경우 빼는 경우이다. 점화식을 세우면 dp[i] = 1 + dp[i // 3] 또는 dp[i] = 1 + dp[i // 2] 그리고 dp[i] = 1 + dp[i - 1] 가 될것이다. 3가지 경우로 구분하고 3또는 2로 나눌때 1을 뺀 값과 비교하여 어떤값이 최솟값인지 구분하여 저장한다. 3과 2의 공배수인 6의 경우 3으로 나눌때와 2로 나눌때 어떤 값이 최소값인지 구분한다.