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

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

1463번: 1로 만들기

1로 만들기 문제

주어진 숫자를 요구조건에 맞춰서 1로 만들 경우의 최소 연산 수를 구하는 문제

다이나믹 프로그래밍을 활용하여 해결할 수 있었다.

📌문제 접근 포인트

1. 요구 제한 시간이 굉장히 짧다. 단순 완전 탐색 등의 방법이 아닌 다이나믹 프로그래밍 방법을 생각해보자.
2. 2가지 방향을 생각할 수 있다. 일반적인 다이나믹 프로그래밍 처럼 DP 1부터 X까지 규칙을 찾아 만들어 가는 방법이 있고, X부터 규칙에 맞춰 1로 찾아 갔을 때의 최소 연산을 찾는 방법이 있다.
3. 요구 조건 대로 X가 3으로 나누어 떨어지면 min(dp[i//3]+1, dp[i]) 비교 
X가 2로 나누어 떨어지면 min(dp[i//2]+1, dp[i]) 비교
1을 뺄 경우 do[i] = dp[i-1] +1
의 조건 대로 다이나믹 프로그래밍을 구현해주면 성공

⚙ 내가 푼 정답 코드 1 (일반적인 다이나믹 프로그래밍)

# 다이나믹 프로그래밍 (1 -> X)
# 상대적으로 느린 속도
import sys
X = int(sys.stdin.readline())
dp = [0]*(X+1)
for i in range(2,X+1):
    dp[i] = dp[i-1] + 1
    if i % 3 == 0:
        dp[i] = min(dp[i//3]+1, dp[i])
    if i % 2 == 0:
        dp[i] = min(dp[i//2]+1, dp[i])

print(dp[X])

⚙ 내가 푼 정답 코드 2 (X에서 1로 최소를 탐색하기)

# X -> 1 탐색
# 상대적으로 빠른 속도
import sys
X = int(sys.stdin.readline())
arr = [0] * (X+1)
dp = [X]
if X == 1:
    print(0)
else :
    while not arr[1]:
        temp = []
        for i in dp:
            if i % 3 == 0 and not arr[i//3]:
                arr[i//3] = arr[i] + 1
                temp.append(i//3)
            if i % 2 == 0 and not arr[i//2]:
                arr[i//2] = arr[i] + 1
                temp.append(i//2)
            if arr[i-1] == 0:
                arr[i-1] = arr[i] + 1
                temp.append(i-1)
        dp = temp
    print(arr[1])

⚙ 내가 푼 정답 코드 3 (향상된 다이나믹 프로그래밍 활용)

# 향상된 다이나믹 프로그래밍
# 중복을 제외하기에 빠른속도 및 적은 메모리 소비
def find(n):
    if n in dp.keys():
        return dp[n]

    if n % 3 == 0 and n % 2 == 0:
        dp[n] = min(find(n//3) +1, find(n//2) + 1)
    elif n % 3 == 0:
        dp[n] = min(find(n//3) +1, find(n-1) + 1)
    elif n % 2 == 0:
        dp[n] = min(find(n//2) +1, find(n-1) + 1)
    else : 
        dp[n] = find(n-1) + 1
    return dp[n]

import sys
X = int(sys.stdin.readline())
dp = {1:0}
print(find(X))