문제
정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다
3. 1을 뺀다
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.
입력
첫째 줄에 1보다 크거나 같고, 10^6보다 작거나 같은 자연수 N이 주어진다.
출력
첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.
둘째 줄에는 N을 1로 만드는 방법에 포함되어 있는 수를 공백으로 구분해서 순서대로 출력한다.
이 문제는 입력값의 최대가 10^6으로 매우 큰 반면, 시간 제한은 0.5초이므로 시간 복잡도를 신경쓰지 않으면 시간 초과가 날 가능성이 높다.
풀이 1 : 일반적인 bfs
import sys
from collections import deque
n = int(sys.stdin.readline())
q = deque(); q.appendleft((n,[n])); result = []
while q:
curr, hist = q.pop()
if curr == 1: result = hist; break
if not curr % 3:
nc = (curr//3); nl = [nc]; nl.extend(hist)
q.appendleft((nc, nl))
if not curr % 2:
nc = (curr//2); nl = [nc]; nl.extend(hist)
q.appendleft((nc, nl))
nc = (curr-1); nl = [nc]; nl.extend(hist)
q.appendleft((nc, nl))
print(len(result)-1)
print(" ".join(map(str,reversed(result))))
q에 현재값과 현재까지 지나온 경로를 모두 포함하는 리스트를 함께 저장하는 방식이다. 현재값이 갱신될 때, 리스트에 갱신된 값을 추가하여 경로를 추가하고 이를 q에 넣는 방식인데, 현재까지의 모든 경로를 복사하여야 하므로 시간이 오래 걸리게 된다.
풀이 2 : bfs + dp
import sys, copy
from collections import deque
n = int(sys.stdin.readline())
q = deque(); q.appendleft(n)
d = [[] for _ in range(n+1)]; d[n].append(n)
while q:
curr = q.pop()
if curr == 1: break
if not curr % 3:
nc = (curr//3)
if not(d[nc]) or len(d[nc]) > len(d[curr])+1:
d[nc] = copy.deepcopy(d[curr]); d[nc].append(nc)
q.appendleft(nc)
if not curr % 2:
nc = (curr//2)
if not(d[nc]) or len(d[nc]) > len(d[curr])+1:
d[nc] = copy.deepcopy(d[curr]); d[nc].append(nc)
q.appendleft(nc)
nc = (curr-1)
if not(d[nc]) or len(d[nc]) > len(d[curr])+1:
d[nc] = copy.deepcopy(d[curr]); d[nc].append(nc)
q.appendleft(nc)
print(len(d[1])-1)
print(" ".join(map(str,d[1])))
현재까지의 최단 경로만을 저장하는 dp테이블을 선언하고,
초기 값을 넣어 세팅해 준다. 이후 dp테이블이 비어있는 경우 혹은 더 작은 경로가 존재하는 경우에만 dp테이블을 갱신하도록 한다.
bfs 과정에서 각 경로의 길이를 비교하고, 저장된 경로보다 작은 경로일 경우에만 갱신을 허용하기 때문에, 경로를 복사하는 과정에서 낭비되는 시간을 줄일 수 있어 수행 시간을 절약할 수 있는 방식의 풀이이다.