[BOJ] 1463_1로 만들기_Python

배너를 클릭시 문제로 넘어갑니다.

문제

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

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

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

입력

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

출력

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

---

아이디어

DP문제의 대표적인 유형 중 하나라고 생각하여 접근하였다.

처음에는 3과 2인 공배수를 이용하여 나머지가 0부터 5까지의 6가지 경우를 고려하여 코드를 짰었으나, 중간에 비는 값이 생겨서 폐기하였다.

두번쨰로는 총 3가지 케이스(3으로 나누기, 2로 나누기, 1을 빼기)를 비교하여 가장 작은 값을 알고 있는 값의 다음 값으로 적용시키는 것이다.

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

이 수식을 통해 dp[i]값을 먼저 1을 빼기 전의 값으로 설정한 뒤, 3으로 나눈 몫과 2로 나눈 몫을 차례로 계산하여 작은 값을 dp[i]에 적용시키는 것으로 게산하였다. 그렇게 하면 dp[i-1]과 dp[i//3], 그리고 dp[i//2]를 모두 비교할 수 있기 때문이다.

import sys
sys.stdin = open('input.txt')

n = int(input())
dp = [0] * (n + 1)	

for i in range(2, n + 1):

    dp[i] = dp[i - 1] + 1
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i // 3] + 1)	
    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i // 2] + 1)
print(d[n])