접근
제시된 연산을 활용하여, 주어진 수를 1로 만드는 최소 계산 횟수를 구하면 된다.
어떤 자연수X(1 <= x < 10^6 + 1)에 대하여
1. (X가 3의 배수일 경우) X를 3으로 나눈다.
2. (X가 2의 배수일 경우) X를 2로 나눈다.
2. X에서 1을 뺀다.
얼핏 보고 중간 연산 결과가 무조건 최소 수만을 반환하면 최소 연산 횟수를 구할 수 있다고 생각할 수 있으나 그렇지 않다. 예를 들어 100의 경우 최소 연산 횟수는 7 (100 -> 99 -> 33 -> 11 -> 10 -> 9 -> 3 -> 1)이다.
결국 모든 경우를 탐색하여야 하는 완전 탐색 문제라는 사실을 알 수 있다.
문제는 시간 제한이 상당히 빡빡하다는 것이다. 순수하게 완전 탐색하는 코드를 제출하면 백이면 백 시간을 초과할 것이다.
순수한 완전 탐색 코드
from sys import stdin
X = int(stdin.readline())
def solve(x):
if x == 1: # 기저 사례: x == 1인 경우
return 0
result = solve(x - 1) + 1 # case 1: x - 1 연산
if x % 2 == 0: # case 2: x // 2 연산
tmp = solve(x // 2) + 1
if tmp < result:
result = tmp
if x % 3 == 0: # case 3: x // 3 연산
tmp = solve(x // 3) + 1
if tmp < result:
result = tmp
return result
print(solve(X))
X = 100 정도까진 잘 계산하는 것 같지만, X = 200만 넣어도 연산이 매우 느리다는 것을 알 수 있다.
코드를 보면 중복되는 계산이 많음을 알 수 있는데, 예를 들어 X = 6인 경우 X = 3을 두 번, X = 2를 세 번 중복 계산한다.
이럴 때 요긴하게 쓸 수 있는 풀이 전략이 동적 계획법이다. X = n의 최소 계산 횟수를 구하고자 할 때 X = p인 경우의 최소 연산 횟수를 중복 연산하는 경우가 생길 수 있으므로, X = p인 경우의 최소 계산 횟수를 최초로 연산할 때 그 결과를 배열 cache에 저장해두는 것이다.
동적 계획법을 적용한 코드
from sys import stdin
X = int(stdin.readline())
def solve(x):
if x == 1: # 기저 사례: x == 1인 경우
return 0
result = solve(x - 1) + 1 # case 1: x - 1 연산
if x % 2 == 0: # case 2: x // 2 연산
tmp = solve(x // 2) + 1
if tmp < result:
result = tmp
if x % 3 == 0: # case 3: x // 3 연산
tmp = solve(x // 3) + 1
if tmp < result:
result = tmp
return result
print(solve(X))
파이썬의 한계인지, 이 코드는 최대 입력(10^6)에서 세그멘테이션 오류를 내며 테스트를 통과하지 못했다. 따라서 나는 동일한 개념을 적용한 반복문 기반의 bottom-up 방식의 코드를 짰고, 이 코드는 테스트를 통과하였다.
bottom-up 방식의 코드
from sys import stdin
x = int(stdin.readline())
EMPTY = -1
cache = [EMPTY for _ in range(x + 1)]
cache[0] = cache[1] = 0
for i in range(2, x + 1):
cache[i] = cache[i - 1]
if i % 3 == 0 and cache[i // 3] < cache[i]:
cache[i] = cache[i // 3]
if i % 2 == 0 and cache[i // 2] < cache[i]:
cache[i] = cache[i // 2]
cache[i] += 1
print(cache[x])
