백준 1463번. 1로 만들기 (Python / 파이썬)

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
 1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
 2. X가 2로 나누어 떨어지면, 2로 나눈다.
 3. 1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 10^6보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

---

문제 풀이

1로 만들기 문제는 세 가지 연산을 적절히 사용해 1을 만드는데,

연산을 사용하는 횟수가 최소가 되도록하는 문제입니다.

이 문제는 Dinamic Programming (DP) 문제로 메모이제이션 기법을 사용하여 해결할 수 있습니다.

 

먼저, 최소값을 저장해줄 배열 dp를 만듭니다.

만약 입력 정수가 10이라면 0~10까지 index로 배열을 만들어줍니다.

이때 index는 계산할 정수로 여깁니다.

앞의 index부터 차례로 수행해 나가는데, 

-index가 3으로 나누어 떨어지면, 3으로 나눈 나머지 index에 저장된 값에 1을 더해줍니다.

-index가 2로 나누어 떨어지면, 2로 나눈 나머지 index에 저장된 값에 1을 더해줍니다.

-index에서 1을 뺀 index에 저장된 값에 1을 더해줍니다.

그리고 이 세가지 연산중 최소 값을 현재 index의 값으로 갱신시켜줍니다.

이 과정을 index 10까지 반복하면 항상 최소값만을 저장하게 되므로 정수 10이 주어졌을 때

최소 연산 횟수를 구할 수 있습니다.

---

My Code

n = int(input()) 

dp = [0] * (n + 1) 

for i in range(2, n + 1):
    # 1을 빼는 경우 
    dp[i] = dp[i - 1] + 1  

    # 3으로 나누는 경우
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i // 3] + 1)
    
    # 2로 나누는 경우 
    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i // 2] + 1)

print(dp[n])