BOJ / 1463 / 1로 만들기 / Python

이전에 풀었던 문제인데 못 풀었다.
기록을 보니 이전에도 못 풀어서 결국 구글링으로 해결했던 문제였다.
역시나 머리에 아무것도 안 남았던 거다 .. !

✍️👀

처음에 재귀로 풀려다가 시간초과가 계속 떴다. DP로 해결해야 하는 문제라고 한다.

Dynamic Programming

다이나믹 프로그래밍은 다음의 조건을 만족할 때 사용할 수 있다.

1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

Memoization 다이나믹 프로그래밍을 구현하는 방법 중 하나로, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미한다. ‘캐싱’ 이라고도 한다.

리스트로 구현한다.
다이나믹 프로그래밍을 재귀적으로 수행하다가 같은 정보가 필요할 때에 리스트에서 값을 그대로 가져온다.

💻 code

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

X = int(input())
dp = [0] * (X + 1)

for i in range(2, X+1):

    # 우선 -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[-1])

크기 X+1인 dp 리스트를 준비한다.
이때 dp는 각 해당 인덱스 숫자가 1이 되는 최소 횟수를 담게 된다.
예를 들어 dp[3]은 숫자 3이 1이 되는 최소 횟수다.

정수 X가 10인 경우를 살펴보면 10을 1로 만드는 최소 횟수는

1. 9(= 10 - 1)가 1이 되는 최소 횟수 + 1 (10 - 1 연산)
또는
2. 5( = 10 // 2)가 1이 되는 최소 횟수 + 1 (10 // 2 연산)

1, 2 값 중 더 작은 값이 된다.

예시로 든 10은 3으로 나누어지지 않았지만 만약 3으로 나누어 떨어지는 숫자라면

3. 입력숫자//3 이 1이 되는 최소 횟수 + 1 (입력숫자 // 3 연산)

이 추가되며 1, 2, 3 중에서 최솟값을 구하면 된다.

Reference

• 나동빈, ⌜이것이 취업을 위한 코딩 테스트다 with 파이썬⌟