[Python]1463번, 1로 만들기

목차

 

문제

 

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지이다.

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

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

 

입력

 

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

 

출력

 

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

 

풀이

 

지난 문제에서 두 가지 값의 조합으로 최솟값을 만들었던 것에 비해,

 

이번 문제에서는 세 가지 연산을 이용해 최솟값을 찾는다.

 

먼저 0으로 초기화한 (N + 1) 크기의 dp리스트를 만들고 2부터 시작해 N까지 반복문을 돌며 리스트를 채워나간다.

 

여기서 2부터 시작하는 이유는 dp[1]은 당연히 0이어야 하기 때문이다.

 

위와 같이 기본적으로는 같은 아이디어를 공유하지만 여기서는 구현의 순서가 살짝 중요하다.

 

자세한 건 코드를 보며 이야기하자.

 

Python

 

import sys

N = int(sys.stdin.readline().rstrip())

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])

순서가 중요한 부분은 반복문의 첫 줄에 나오는

    dp[i] = dp[i - 1] + 1

인데, 생각해 보면 당연하게도 이 값으로의 초기화가 먼저 이루어져야 한다.

 

그 이후의 연산, 그러니까 2로 나누어 떨어질 때와 3으로 나누어 떨어질 때의 로직 순서는 중요하지 않다.

 

N까지 채운 후에 결과를 출력하면 끝.