[백준] 1463번 - 1로 만들기

📩 출처

문제

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

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

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

입력

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

출력

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

👉 생각

• 2부터 10까지 1로 갈 수 있는 최소값을 적어 놓고 보니, DP로 접근할 수 있다는 것을 확인할 수 있었다. n의 입장에서는 3가지 선택권이 주어진다. 1을 빼거나, 3으로 나누거나, 2로 나누거나!
• 각각의 선택을 하고나서 나오는 숫자들은 또 3가지 선택을 할 수 있다. 즉 n이 어떤 선택을 통해 그 숫자로 이동을 하면 다시 그 숫자는 3가지 선택을 하면서 1로 가게 된다.
• 따라서 dp 리스트의 값을 n(인덱스)이 1까지 가는 최소 횟수로 입력하게 되면, n이 증가할 때마다 n 보다 작은 값들 중 1로 가는 최소 횟수가 입력된 정보를 통해 쉽게 찾을 수 있다.

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:
        # 6 > 3 > 1로 가는 방법
        dp[i] = min(dp[i], dp[i//2] + 1)

print(dp[n])