[python/백준] 1463. 1로 만들기(S3)

📌 문제 탐색하기

👉 문제바로가기
N: 정수(1<=N<=10^6)
정수 N에 사용할 수 있는 연산은 다음과 같습니다.

• N이 3으로 나누어 떨어지면, 3으로 나눕니다.
• N이 2로 나누어 떨어지면, 2로 나눕니다.
• 1을 뺍니다.

정수N이 주어진 경우 연산 3개를 활용하여 1을 만들 수 있는 연산 횟수의 최솟값을 구하면 됩니다.

이 문제에서 우리는 다양한 경우를 생각해볼 수 있습니다.

• N = 2인 경우: 2 -> 1(1가지)
• N = 3인 경우: 3 -> 1(1가지)
• N이 4보다 큰 경우
  • 2, 3으로 모두 나누어 떨어지지 않는 경우 먼저 1을 뺍니다.
  • 2로 나누어지고 3으로 나누어 떨어지지 않는 경우
    case 1) 2로 바로 나눈 이후 해당 숫자에 대해 연산 횟수 구하기
    case 2) 1을 먼저 뺀 후 해당 숫자에 대해 연산 횟수 구하기
  • 3으로 나누어지고 2로 나누어 떨어지지 않는 경우
    case 1) 3으로 바로 나눈 이후 해당 숫자에 대해 연산 횟수 구하기
    case 2) 1을 먼저 뺀 후 해당 숫자에 대해 연산 횟수 구하기
  • 2로 나누어지고 3으로 나누어지는 않는 경우
    case 1) 2로 바로 나눈 이후 해당 숫자에 대해 연산 횟수 구하기
    case 2) 3으로 바로 나눈 이후 해당 숫자에 대해 연산 횟수 구하기

이렇게 케이스들을 분리한 후 연산 횟수의 최솟값을 구하면 되겠네요.

📌 알고리즘 선택

다이나믹 프로그래밍으로 문제를 해결할 수 있는지 판단해봅시다. 이해하기 쉽도록 예를 들어보겠습니다.

N이 9인 경우

• 방법1: 9 -> 3 -> 1
• 방법2: 9 -> 8 -> 4 -> 2 -> 1

9의 경우 3의 배수이기 때문에 바로 3으로 나눌 수도 있고, 1을 뺀 후 2로 나누어 볼 수 있습니다. 두가지 경우를 고려하셔 연산 횟수를 구해보고 최솟값을 구하면 되겠네요.

방법 1에서 9가 3이 되는 순간 3에서 1까지 가는 경우에 대한 연산 횟수를 알고있다면 굳이 반복해서 계산하지 않고 이전에 구해놓은 값3->1의 연산 횟수의 최솟값을 그대로 가져와서 사용할 수 있겠네요. 이전 단계에서 구한 값을 다음 계산에서 활용할 수 있으므로 DP를 사용하면 되겠습니다.

시간복잡도

N이 될 때까지 while루프를 반복하면서 작은 숫자부터 최소 연산 횟수를 dp리스트에 저장하기 때문에 시간복잡도는 O(N)이 됩니다. N의 최댓값은 10^6이므로 충분히 주어진 시간 내에 연산이 가능합니다.

📌 코드 설계하기

1. 정수 N을 Input받고, 연산 횟수의 최솟값을 저장할 리스트를 초기화합니다.
2. dp[2] = 1, dp[3] = 1로 초기값을 설정합니다.
3. 4부터 시작해서 값을 증가시키며 dp리스트에 값을 넣습니다.
4. N이 입력한 값이 되면 dp[N]을 출력합니다.

📌 정답 코드

N = int(input())
dp = [0 for _ in range(N+1)]    #연산 횟수를 저장할 리스트

if N >= 2:
    dp[2] = 1
if N >= 3:    
    dp[3] = 1 
if N > 3:
    i = 4
    while i < (N+1):
        if i % 2 != 0 and i % 3 != 0:
            dp[i] = dp[i-1] + 1  
        elif i % 2 == 0 and i % 3 != 0:
            if dp[i-1] > dp[i//2]:
                dp[i] = dp[i//2] + 1
            else:    
                dp[i] = dp[i-1] + 1
        elif i % 2 != 0 and i % 3 == 0:
            if dp[i-1] > dp[i//3]:
                dp[i] = dp[i//3] + 1
            else:    
                dp[i] = dp[i-1] + 1
        else:   #2의 배수이면서 3의 배수인 경우
            if dp[i//2] > dp[i//3]:
                dp[i] = dp[i//3] + 1
            else:    
                dp[i] = dp[i//2] + 1
        i += 1

print(dp[N])