문제 설명

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 10⁶보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

풀이 코드

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

import sys


def update_counts(v, value_with_counts, count):
    old_count = value_with_counts.get(v, count)
    value_with_counts[v] = min(old_count, count)


n = int(sys.stdin.readline())

value_with_counts = {n: 0}

while value_with_counts:
    v = max(value_with_counts)
    c = value_with_counts.pop(v)
    if v <= 1:
        print(c)
        break

    if v % 3 == 0:
        update_counts(v // 3, value_with_counts, c + 1)
    elif v % 3 == 1:
        update_counts((v - 1) // 3, value_with_counts, c + 2)
    else:
        update_counts((v - 2) // 3, value_with_counts, c + 3)

    if v % 2 == 0:
        update_counts(v // 2, value_with_counts, c + 1)
    else:
        update_counts((v - 1) // 2, value_with_counts, c + 2)

CHECK!

시간초과를 막기 위해, 3과 2로 나누어지지 않을 때는 나머지만큼 뺀 후 나누는 방식으로 진행
매번 1을 뺀 값을 리스트에 더하는 것 보다 경우의 수가 줄게 됨

중복된 코드 제거를 위해 update_counts 함수를 만듬