[BOJ] 1463번 : 1로 만들기 (Python)

🔒 문제

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

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

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

⌨ 입력

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

🖨 출력

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

📚 예제

Ex1)

2

'''python
1
'''

Ex2)

10

'''python
3
'''

📌 풀이

dp[정수N+1] 행렬을 만든다. (N이 아니라 N+1개의 인덱스를 만드는 이유는 숫자 헷갈리기 싫어서,,,ㅎㅎ)
각 인덱스에 저장되는 수는 인덱스 수를 연산했을 때 연산 횟수의 최솟값이다.
위에서 말한 연산 세 가지를 모두 행해보고 가장 작은 최솟값을 행렬에 저장 할 것이다.

1. dp[1] = 0

숫자 1은 연산할 필요가 없으니까 연산 횟수는 0이다.

2. n이 2이상일 때 부터 연산을 시작한다.

n의 최소의 연산횟수를 찾는 방법은 3가지가 있다.

1) -1 연산을 했다고 가정
dp[n] = dp[n-1] + 1

2) 3으로 나눠 진다면, 나누기 3 연산을 했다고 가정
dp[n] = dp[n//3] + 1

3) 2로 나눠진다면, 나누기 2연산을 했다고 가정
dp[n] = dp[n//2] + 1

위 3가지 모두를 사용할 수 있거나, 두개만 사용할 수 있거나, -1연산 하나만 사용할 수 있는 경우가 존재한다.
-1 연산은 어떤 경우에도 사용될 수 있으니, 기본적으로 -1 연산을 하고,
n을 3이나 2로 나눴을때 나누어 떨어지는 경우들을 -1 연산을 했을때의 연산 수를 비교하여 더 적은 연산 수를 dp[n]의 값으로 한다.

🔑 python 코드

import sys
N = int(sys.stdin.readline())
dp = [0 for _ in range(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(dp[N])