[Python] 백준 1463번 1로 만들기(실버3)

문제

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

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

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

입력

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

출력

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

예제 입력 1

2

예제 출력 1

1

예제 입력 2

10

예제 출력 2

3

---

풀이

Queue를 활용해 최단 반복 횟수를 구하는 문제입니다.

Point

• Queue
• 그래프 탐색
• 너비 우선 탐색

---

소스코드

from collections import deque

count = 0
queue = deque()
queue.append(int(input()))

def one_iter(queue):
    next_queue = deque()
    while queue:
        n = queue.popleft()
        if n == 1:
            return None
        if n%3 == 0:
            next_queue.append(n//3)
        if n%2 == 0:
            next_queue.append(n//2)
        next_queue.append(n-1)
    return next_queue

while queue:
    count+=1
    queue = one_iter(queue)
print(count-1)

 

문제는 쉬워보이지만, 그래프 탐색 알고리즘을 많이 접하지 않았다면 쉽게 해답이 떠오르지 않습니다.

처음 생각나는 그리디 알고리즘은 10 과 같은 예시의 정답을 올바르게 구해주지 못합니다.

이럴 때에는 최소 깊이를 도달할 때까지 병렬적으로 재귀함수를 호출할 수 있는 너비 우선 탐색을 활용해 봅시다.

 

Line 1~5

from collections import deque

count = 0
queue = deque()
queue.append(int(input()))

 

collections의 deque는 나중에 쓰일 queue의 deque를 구현할 수 있게 해 줍니다.

 

원하는 결과값인 count=0으로 세팅해주고,

queue의 초기 세팅을 위해 input()값을 받아줍니다.

이후 이해를 돕기 위해 10이 input으로 주어졌다고 가정하겠습니다.

(ex. queue = [10])

Line 7~18

def one_iter(queue):
    next_queue = deque()
    while queue:
        n = queue.popleft()
        if n == 1:
            return None
        if n%3 == 0:
            next_queue.append(n//3)
        if n%2 == 0:
            next_queue.append(n//2)
        next_queue.append(n-1)
    return next_queue

 

one_iter 함수를 정의해서 한번의 실행 (-1 혹은 /2 혹은 /3)을 정의해 주고, 다음 실행에서 쓰일 queue를 반환합니다.

 

First iteration

queue에 남아있는 값을 순차적으로 빼냅니다. ( n = queue.popleft() = 10) ( queue = [ ] )

10은 2로 나누어떨어지기 때문에, next_queue = [ 5 (=n//2) , 9 (=n-1) ] 가 됩니다.

 

Second iteration

queue에 남아있는 값을 순차적으로 빼냅니다. ( n = 5, 9 )

5 에 대해 next_queue = [ 4 ]

9 에 대한 next_queue = [ 3, 8 ]

최종적으로 next_queue = [ 4, 3, 8 ]

 

Third iteration

queue에 남아있는 값을 순차적으로 빼냅니다. ( n = 4, 3, 8 )

4 에 대해 next_queue = [ 2, 3 ]

3 에 대한 next_queue = [1, 2 ]

8 에 대한 next_queue = [4, 7 ]

최종적으로 next_queue = [ 2, 3, 1, 2, 4, 7 ]

 

Fourth iteration

queue에 남아있는 값을 순차적으로 빼냅니다. ( n = 2, 3, 1, . . .  )

이 때 n == 1 에 걸리게 되므로, 함수는 None을 반환하며 끝나게 됩니다. ( 전 단계에서 멈추게 할 수도 있습니다 )

Line 20~23

while queue:
    count+=1
    queue = one_iter(queue)
print(count-1)

 

queue가 None이 될 때 까지 one_iter를 반복해 next_queue를 구해줍니다.

1을 발견하면 queue가 None이 되지만, 위에서 보이듯, 실제 iteration이 아닌 마지막 단계까지도 count 했기 때문에,

마지막 출력값에는 count-1을 해 줍니다.