문제

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

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

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

문제를 보면 DP (Dynamic Programming) 문제의 일종이라는 것을 알 수 있다.

풀이 방법 1

1. $x=2$
   가능한 연산은 2로 나눠주는 것과 1을 빼주는 것이 있다.
   어떤 연산을 수행하더라도 1이 되기 때문에 연산을 한 번만 수행하면 된다.

   when $x=2$, step = 1

2. $x=3$
   가능한 연산은 3으로 나눠주는 것과 1을 빼주는 것이 있다.
   3으로 나눌 경우 바로 1이 된다.
   1을 빼줄 경우 2가 되지만, 2일 때 1을 만들기 위해선 한 번의 연산을 더 해주어야 하기 때문에 3으로 나누는 연산을 취해준다.

   when $x=3$, step = 1

3. $x=4$
   가능한 연산은 2로 나눠주는 것과 1을 빼주는 것이 있다.
   2로 나눠줄 경우, 2가 된다. 2일 때 1을 만들기 위해선 한 번의 연산을 더 해주어야 하기 때문에 이 때 총 연산은 2 (1+1) (2를 나눠주는 연산을 했기 때문에)가 된다.
   1을 빼 줄 경우, 3이 되는데, 3일 때 필요한 총 연산은 1이기 때문에 필요한 총 연산은 2 (1+1) (1을 빼주는 연산을 했기 때문에)가 된다.

   when $x=4$, step = 2

4. $x=5$
   가능한 연산은 1을 빼주는 것밖에 없다.
   1을 빼면 4가 되는데 4가 1이 되기 위해 필요한 연산이 2회므로 총 필요한 연산은 3 (2+1)이 된다.

   when $x=5$, step = 3

5. $x=6$
   모든 연산이 가능하다.
   3으로 나눠줄 경우 2가 되는데, 2의 step이 1이기 때문에 필요한 총 연산은 2가 된다.
   2로 나눠줄 경우 3이 되는데, 3의 step이 1이기 때문에 필요한 총 연산은 2가 된다.
   1을 빼줄 경우, 5가 되는데, 5의 step이 3이기 때문에 필요한 총 연산은 4가 된다.
   2가 최소값이기 때문에 2를 취해준다.

   when $x=6$, step = 2

이를 일반화하자면, 2부터 숫자 $n$을 하나씩 높여가면서 가능한 연산 결과 $n/3$, $n/2$, $n-1$를 구한다. 그리고 해당 숫자의 step에다 1을 더한 값 중에 최소값을 취하여 $n=x$일 때의 총 연산 횟수를 반환하면 된다.

코드

풀이 1.1

import sys 
input = sys.stdin.readline

# get input
x = int(input())

memory = [[0, []]] # [steps to one, routes have passed]

for n in range(2,x+1):
    max_step = x

    op3 = int(n/3) if n%3 == 0 else None
    op2 = int(n/2) if n%2 == 0 else None
    op1 = n-1

    op_result = [(memory[x-1],x) for x in [op1, op2, op3] if x is not None] #  possible operations
    min_ = min(op_result, key = lambda x : x[0])

    min_step = min_[0][0]
    min_route = min_[0][1]
    min_num = min_[1]

    memory.append([min_step+1, min_route + [min_num]])

answer = memory[-1]
print(answer[0]) # steps
route = answer[1] + [x]
route = route[::-1]
print(*route)

3가지 연산을 모두 실행한 후에 가장 작은 값을 min 함수로 가져왔다.
그러나 해당 코드를 python으로 돌렸을 때 시간초과가 발생하여 pypy3으로 돌렸다.

pypy3으로 돌렸을 때 1616ms가 소요되었다.

풀이 1.2

import sys 
input = sys.stdin.readline

# get input
x = int(input())

memory = [[0, []]] # [steps to one, routes have passed]

for n in range(2,x+1):

    lowest_step = n
    lowset_op_result = None
    
    if n%3 == 0: # devide by 3

        op3 = int(n/3)
        step = memory[op3-1][0] +1

        if step < lowest_step:
            lowest_step = step
            lowest_op_result = memory[op3-1][1] + [op3]

    if n%2 == 0:

        op2 = int(n/2)
        step = memory[op2-1][0] +1

        if step < lowest_step:
            lowest_step = step
            lowest_op_result = memory[op2-1][1] + [op2]

    op1 = n-1
    step = memory[op1-1][0] +1

    if step < lowest_step:
            lowest_step = step
            lowest_op_result = memory[op1-1][1] + [op1]

    
    memory.append([lowest_step, lowest_op_result])

answer = memory[-1]
print(answer[0]) # steps
route = answer[1] + [x]
route = route[::-1]
print(*route)

3가지 연산을 전부 실행한 후에 min값을 찾는 것이 아니라, 연산을 실행하면서 동시에 min값을 업데이트해주었다. 결과적으로는 pypy3으로 돌렸을 때 1192 ms 로 전보다 더 빠름을 확인할 수 있었다.

풀이 방법 2

풀이 방법 1에 따른 결과를 표로 정리해보았다.

우선 숫자 $n$이 3의 배수인 경우, $n$이 홀수이든 짝수이든 3으로 나누는 게 최적의 방법임을 확인할 수 있다.

또한, 숫자 $n$을 3으로 나눴을 때의 나머지가 2라면, $n$이 짝수일 때는 2로 나눠주고 홀수일 때는 1을 빼주는 것이 최적의 방법임을 확인할 수 있다.

숫자 $n$을 3으로 나눴을 때의 나머지가 2라면, $n$이 홀수 일 때 1로 빼주는 것이 최적의 방법임을 확인할 수 있다.

그러나 $n$이 짝수일 때는 상황에 따라 2로 나누는 것이 적절할 수도, 1로 빼는 것이 적절할 수가 있다. 해당 부분에 대해서는 규칙성을 파악하지 못했기에, 해당 부분이 발생했을 시에는 BFS로 최적을 구해보고자 하였다.

풀이 2.1

import sys 
from collections import deque

def by_queue(x):
    queue = deque([(x,0, [])]) # num, step, route

    while queue:
        num, _, _ = queue[0]

        if num == 1: # 원하는 걸 찾았을 때 탈출
            break

        num, step, route = queue.popleft() # get the top
        route_copy = route.copy()
        route_copy.append(num)

        if num%3 == 0: # 나머지가 0일 때
            num /= 3
            step += 1
            queue.append((int(num),step,route_copy))

        elif num%3 == 2: # 나머지가 2일 때
            if num%2 == 0 : # 짝수일 때
                num /= 2
            else:
                num -= 1
            step += 1
            queue.append((int(num), step, route_copy))

        else: # 나머지가 1일 때
            if num%2 == 0 : #짝수일 때
                queue.append((int(num/2), step+1, route_copy))
            queue.append((num-1, step+1,route_copy)) # 짝수일 때와 홀수일 때 모두

    answer = queue[0]
    total_steps = answer[1]
    route = answer[-1]+[1]

    return total_steps, route

그러나 이는 틀린 문제 풀이이다.

가령 321이라는 숫자가 있다고 해보자. 만약 위 식대로 진행한다면 [321, 107, 106, 53, 52, 26, 13, 12, 4, 2, 1]로 총 10번의 연산을 한다. 그러나 실제 최적 해는 [321, 320, 160, 80, 40, 20, 10, 9, 3, 1]로 3의 배수임에도 불구하고 1을 빼는 연산을 먼저 수행하는 것이 더 빠르다.

즉 풀이 2의 규칙에 예외가 발생한 것이다. 해당 예외를 예측하지 못했기에 틀린 풀이가 되었다.