1463번 Python

단순히 문제 해결보다는 문제에서 의도하고자 하는 것이 무엇인지 알아가면서 정리하려고 한다. 어렴풋이 어떻게 풀었는지 기억은 나지만 내가 왜 이렇게 했는지 잊어버렸다. 그렇기에 더욱 더 문제에 대한 정리가 필요한 시점이라고 생각했고 DP의 기초 문제부터 천천히 접근하겠다.

 

1463번 문제의 경우에는 1로 만들 수 있는 최적의 해를 구하는 것을 목표로 둔다. 

10 -> 5 -> 4 -> 2 -> 1
10 -> 9 -> 3 -> 1

문제에도 적혀있는 부분이긴 하지만 10의 경우에는 4번이 아닌 3번만으로도 1을 만들 수 있기에 이것을 어떻게 구현해 나가야 하는지를 생각해보아야겠다.

 

여기서 dp를 사용하는 것이다. 각 숫자별로 가장 최적의 해를 구할 수 있는 값을 기억해둔다면 그 값을 꺼내 사용하면 될 것이다. 이를 메모이제이션이라고 칭할텐데 용어 같은 것은 모른다고 해도 의도하고자 하는 것은 숫자가 만들어지는 최적의 해를 미리 저장해두는 로직을 생각해보자.

 

위에 적은 10을 예시로 들어가보겠다. 10이 1이 되는 것에 있어서 방법은 2가지가 있다. 9까지 이미 1이 되는 최적의 해를 구해둔 테이블이 존재한다고 가정했을 때, 5가 1이 되는 최적의 해와 9가 1이 되는 최적의 해 둘 중 가장 작은 값이 10이 1이 되는 최적의 해라고 볼 수 있다.

 

import sys

n = int(sys.stdin.readline())
dp = [0] * 1000001 # 문제에서 10의 6제곱이 최댓값으로 지정되어 이에 대해 1을 더해줘 1에 해당하는 것이 1번째 인덱스라고 칭함

for i in range(2, n + 1):
    dp[i] = dp[i - 1] + 1 # 1을 뺀 최적의 해
    if i % 2 == 0: dp[i] = min(dp[i], dp[i // 2] + 1) # 1을 뺀 최적의 해와 인덱스가 2로 나누어지는 최적의 해를 비교해 가장 작은 값을 dp 테이블에 담음
    if i % 3 == 0: dp[i] = min(dp[i], dp[i // 3] + 1) # 위와 동일하나 나누어지는 값이 3

print(dp[i])

2부터 시작하여 입력받은 n 값까지의 각각 최적의 해를 구하고 10의 예시처럼 9의 최적의 해와 5의 최적의 해 중 더 작은 값을 선택하여 10의 최적의 해를 구해주는 식으로 만들면 된다.

 

정리

문제에는 2와 3으로 나눌 수 있는 연산과 1을 빼는 연산이 존재하고 3개의 연산을 적절히 사용하여 1이 되는 최적의 해를 구하면 된다. 즉, 2와 3으로 나눌 수 있다해서 먼저 나누는 것이 아닌 최소로 연산을 이용하는 식을 구하면 되는 것이다. 

 

10의 경우를 생각해보았을 때, 2로 나누어지기도 하지만 1을 뺄 경우도 고려해야한다. 2부터 9까지 각 1이 되는 최적의 해를 먼저 구해준 다음, 5 -> 1이 되는 최적의 해와 9 -> 1이 되는 최적의 해를 비교해 가장 작은 값을 dp 배열에 넣어주면 된다. 이 dp 배열은 모든 최적의 해를 담고 있는 배열을 의미한다.