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

📃문제

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

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

📃입력

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

📃출력

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

📃예제 입력 1

2

📃예제 출력 1

1

📃예제 입력 2

10

📃예제 출력 2

3

📃힌트

10의 경우에 10 → 9 → 3 → 1 로 3번 만에 만들 수 있다.

✏️문제 탐색하기

숫자 N 을 1로 만드는 데 필요한 연산 횟수를 최소화하는 것입니다. 세 가지 연산(나누기 3, 나누기 2, 1 빼기)을 통해 최적의 경로를 찾는 문제.

주어진 조건:

• 숫자 N이 주어졌을 때 세 가지 연산 중 하나를 선택하여 1로 만듭니다
• N이 3으로 나누어떨어지면 N을 3으로 나눕니다.
• N이 2로 나누어떨어지면 N을 2로 나눕니다.
• N에서 1을 뺍니다.
• 가능한 최소 횟수로 1을 만들어야 합니다.

✏️알고리즘 선택

• for 루프는 2 부터 N 까지 O(N) 반복합니다.
• 각 루프에서 3번의 연산(1 빼기, 나누기 2, 나누기 3)을 수행합니다.
• 따라서 전체 시간 복잡도는 O(N)입니다.

동적 프로그래밍 접근법을 사용하여 조합 값을 미리 계산하고 저장하는 방식으로 문제를 해결.

✏️코드 설계하기

1. 숫자 N 을 입력받습니다.
2. dp 배열의 크기를 N + 1 로 설정합니다.
3. 반복문으로 2 부터 N 까지 순회하면서 최소 연산 횟수를 계산합니다.
4. dp[N]에 저장된 값을 출력합니다.

✏️코드 구현

import sys


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

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