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

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

---

문제

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

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

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

입력

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

출력

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

---

접근 방법

  주어진 수를 1로 만드려면 '3으로 나누기 > 2로 나누기 > 1 빼기'의 순으로 값이 줄어드는 속도가 크니까 Greedy 알고리즘으로 풀려고 하면 오답이 된다. 예를 들어, 10이 주어진다면 Greedy하게 계산하면 '10 -> 5 -> 4 -> 2 -> 1'의 순으로 계산된다. 반면, 문제 조건에 따라 10을 1로 만들 수 있는 방법 중 연산 횟수가 가장 적은 방법은  '10->9->3->1'이다.

  즉, 매 순간마다 최선의 선택을 구하는 것이 아니라, 모든 가능한 경우 중에서 최소한의 연산횟수가 걸리는 경우를 찾아야 한다. 연산 결과를 node로, 연산 방법(3으로 나누기, 2로 나누기, 1 빼기)을 node에서 다음 node로 연결되는 edge로 본다면 이 문제를 BFS로 풀 수 있다.

 

# 백준 1463 1로 만들기 https://www.acmicpc.net/problem/1463
# x가 3으로 나누어 떨어지면 3으로 나눈다.
# x가 2로 나누어 떨어지면 2로 나눈다
# 1을 뺀다.
# x를 1로 만드는 연산 횟수의 최솟값을 출력
from collections import deque

def bfs(start):
    q = deque([start])
    while q:
        node = q.popleft()
        if node == 1:
            break

        if node % 3 == 0 and visited[node//3]==0:
            q.append(node//3)
            visited[node//3] = visited[node] + 1 # 계산 횟수 업데이트
        if node % 2 == 0 and visited[node//2] == 0:
            q.append(node//2)
            visited[node//2] = visited[node] + 1
        if visited[node-1] == 0:
            q.append(node-1)
            visited[node-1] = visited[node] + 1

    return visited

x = int(input())
visited = [0] * (x+1)
visited = bfs(x)
print(visited[1]) # 1이 될 때까지 방문한 정점의 수 출력

  문제의 조건대로, node가 3으로 나누어 떨어지면서 node//3을 방문하지 않았다면 node//3을 q에 추가해주고, node가 2으로 나누어떨어지면서 node//2를 방문하지 않았다면 node//2를 q에 추가해준다. 그리고 node-1을 당문하지 않았다면 node-1을 q에 추가해준다. 즉, (위에서 언급한 조건을 만족할 때) 다음에 방문할 정점은 node//3, node//2, node-1이 되는 것이다. 그리고 다음 방문 정점이 추가되는 경우마다 visited에 연산 횟수를 업데이트 해준다.  

  이제 bfs의 시작 정점으로 문제에서 주어지는 수  x를 넣어주면, visited에는 각 인덱스 마다, x에서 해당 인덱스값이 되기 위해 최소 몇 번의 연산을 거쳐야 하는지가 저장된다. 따라서 visited[1]을 출력하면 1이 되기 위한 최소 연산 횟수를 출력할 수 있다.