1로 만들기

 

비효율적으로 푼 내 풀이

#내가 풀어본 비효율적인 방식
from collections import deque

x = int(input())
answer = 0

q = deque([(x, 0), (x-1, 1)])
while True:
    t = q.popleft()
    nx = t[0]
    count = t[1]

    if nx == 1:
        answer = count
        break

    if (nx % 5) == 0:
        q.append((nx // 5, count+1))
        q.append(((nx // 5) - 1, count+2))
    if (nx % 3) == 0:
        q.append(((nx // 3) - 1, count+2))
    if (nx % 2) == 0:
        q.append(((nx // 2) - 1, count+2))

print(answer)

나는 모든 경우의 수를 q에 담아 계산하는 방식으로 풀었다. 비슷한 문제가 백준에 있어서 풀어봤더니 런타임 에러가 떴다. 일단 예시에 나온 26을 입력하니 3이 나오기는 했다.

내 풀이가 틀린 이유는 동일한 연산이 반복되어 계산하는 것을 고려하지 않아서 그런거 같다.

 

교재 풀이

이 문제는 이런식으로 같은 함수가 여러번 나오게 된다.

 

-점화식

사용 가능한 연산에서 가장 작은 것을 구해야한다. 1을 더해주는 이유는 함수의 호출 회수를 구해주기 때문이다.

 

x = int(input())

d = [0] * 30001

for i in range(2, x+1):
    d[i] = d[i - 1] + 1
    if i % 2 == 0:
        d[i] = min(d[i], d[i // 2] + 1)
    if i % 3 == 0:
        d[i] = min(d[i], d[i // 3] + 1)
    if i % 5 == 0:
        d[i] = min(d[i], d[i // 5] + 1)

print(d[x])

이 코드는 d 배열의 인덱스 번호에 들어가는 숫자가 결국 최소 연산 회수인 것이다. 이렇게 보텀업 방식을 사용하면 효율적으로 문제를 풀 수 있다.