[BOJ] 1463 - 1로 만들기

풀이

기본적인 DP 문제이다. 작은 수의 계산 결과를 저장하면서 다음 문제를 해결할 때 이용하면 간편하게 문제를 해결할 수 있다.

 

입력과 출력을 한번 생각해보자.

입력이 1이라면 답은 0, 입력이 2라면 답은 1이다.

 

입력이 4라면 2로 한번 나눠서 2가 될 것이고 2를 1로 만드는 연산 횟수는 먼저 계산했듯 1이다.

입력이 16이 들어온 경우 만약 8을 1로 만드는 최소 횟수를 안다면 그것에 1만 더하면 된다.

 

입출력의 예시를 생각해보면, 작은 숫자를 1로 만드는 연산 횟수를 알고 있다면 더 큰 수일 때 

이 문제를 푸는 핵심은 문제를 최대한 분해한 다음 가장 작은 수에서부터 그것을 1로 만드는 연산 횟수를 구하는 것이다.

 

소스코드에서 n%2, n%3을 더해주는 것은 해당 숫자로 나누어지지 않았을 때 1씩 빼는 경우를 더해주는 것이다.

 

Python3 Code

dp = {1:0, 2:1}

def find(n):
    if n in dp:
        return dp[n]
    
    x = find(n//2) + n%2
    y = find(n//3) + n%3
    
    m = 1 + min(x, y)
    dp[n] = m
    return m

n = int(input())
print(find(n))