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

https://www.acmicpc.net/problem/1463

📌 문제 탐색하기

목표

• 정수 n이 주어졌을 때 세 가지 연산 기법들을 사용하여 1을 만들어 본다.
• 연산을 사용하는 횟수의 최솟값을 출력한다.
• 사용할 수 있는 연산은 다음과 같다.
  1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
  2. X가 2로 나누어 떨어지면, 2로 나눈다.
  3. 1을 뺀다.

입력값

• 정수 n을 입력한다. (1 ≤ n ≤ $10^6$)
• ex)
• 10

출력값

• 세 가지 연산들을 사용하는 횟수의 최솟값을 출력한다.
• ex)
• 3

📌 코드 설계하기

해결 아이디어

• 시간 제한이 0.15초이므로 재귀나 반복되는 계산을 모두 줄여야한다.
• 수의 규칙을 찾기 위해 쭉 써보면 다음과 같은 결과가 나오게된다.

• 연산을 위해 이미 연산이 되어있는 앞의 숫자를 사용하면 되는 것이다.

그러면 bottom-up / top-down?

• 현재처럼 dp[n] 값을 바로 참조해야하는데 값이 비어있으면 안 되니 bottom-up 방식이 더 낫다고 판단했다.
• dp[1] = 0부터 초기화를 해주고 2나 3으로 나눠질 때 +1을 할지 각 수로 나눌지 선택을 하기로 했다. 최솟값을 선택하면 된다.

📌 정답 코드

import sys

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

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

for i in range(2, n+1):
    dp[i] = 1 + dp[i-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])

• for문
  • 2~n까지 총 n-1번 반복

최종 시간 복잡도: O(N)

📌 다른 풀이

import sys

sys.setrecursionlimit(10**7)

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

dp = [-1] * (n +1)
dp[1] = 0

def solve(x):
    if dp[x] > -1:
        return dp[x]
    result = solve(x -1) + 1

    if x%3 == 0:
        result = min(result, solve(x//3) + 1)
    if x%2 ==0:
        result = min(result, solve(x//2) +1)
    
    dp[x] = result
    return result

print(solve(n))

• 이번에는 탑다운 방식으로 풀어보았다. dp 문제를 풀 때 계속 이렇게 풀어왔어서 이 방식이 조금더 익숙한데 채점하는데 걸리는 시간은 훨씬 오래걸렸다.
• 재귀 깊이 문제로 인해 조금 공간 복잡도 측면에서는 불리한 측면도 있는 코드이다.
• 사실상 같은 시간복잡도 O(N)을 가지지만 계속 solve() 함수를 재귀적으로 호출해야하므로 이번 문제에서는 bottom-up이 훨씬 안정적으로 작동한다.