개요
정수 N이 주어졌을때, 1로 만들 수 있는 최단 경우를 구하는 문제입니다. 조건에 따라 N에 적용할 수 있는 규칙은 다음과 같습니다.
- 3으로 나누어 떨어지면 3으로 나눌 수 있다.
- 2로 나누어 떨어지면 2로 나눌 수 있다.
- 1을 뺀다.
출력조건은 스페셜 저지 문제로, 최단 경우와 중간 히스토리까지 출력해야합니다.
문제풀이
간단한 방법인 완전탐색으로 시작해, 다이나믹 프로그래밍으로 발전시킬 생각을 했습니다.
BFS
큐를 이용해 BFS를 구현했습니다. 큐의 각 값은 히스토리가 담긴 배열입니다.
def bfs(n):
q = deque([[n]])
while q:
state = q.popleft()
bfs(n)
# n이 3일때
# q: [[3]]
큐에서 뽑아낸 배열의 마지막 숫자의 조건을 체크합니다.
- 나누어 떨어지면 나누어 떨어졌을때의 값을 복사한 배열에 추가한채로, 큐에 집어넣습니다.
- 1을 빼는 선택지는 항상 가능하니, 1을 뺀 값도 큐에 넣어줍니다.
def bfs(n):
q = deque([[n]])
while q:
state = q.popleft()
if (state[-1] == 1):
return state
if (state[-1] % 3 == 0):
cur = state[:]
cur.append(state[-1]//3)
q.append(cur)
if (state[-1] % 2 == 0):
cur = state[:]
cur.append(state[-1]//2)
q.append(cur)
cur = state[:]
cur.append(state[-1]-1)
q.append(cur)
bfs(n)
# n이 3일때
# 초기 q상태 : [[3]]
# 조건문 한번 거친 q 상태: [[3,1], [3, 2]] => [3, 1]에서 1이 나왔으므로 탈출
전체코드
from collections import deque
n = int(input())
def bfs(n):
q = deque([[n]])
while q:
state = q.popleft()
if (state[-1] == 1):
return state
if (state[-1] % 3 == 0):
cur = state[:]
cur.append(state[-1]//3)
q.append(cur)
if (state[-1] % 2 == 0):
cur = state[:]
cur.append(state[-1]//2)
q.append(cur)
cur = state[:]
cur.append(state[-1]-1)
q.append(cur)
answer = list(map(str, bfs(n)))
print(len(answer)-1)
print(" ".join(answer))
다이나믹 프로그래밍
BFS는 통과못할 걸 예상했었는데, 채점해보니 통과했습니다. 완전탐색이라 하더라도, 탈출조건(1로 만들었을때)에 도달했을때가 최적의해임을 보장받고 탈출 할 수 있으므로 그나마 빨랐던 것 같습니다. 그래도 불필요한 연산이 많고 시간소요또한 3168ms 로 아슬아슬해 DP로 줄여보려 했습니다.
1 부터 시작해서 각 숫자의 최적의해(최단거리 배열 히스토리)를 저장해두고 재사용하는게 핵심입니다. 가장 간단한 경우인 1일 경우부터 생각해보겠습니다.
dp = [[], [1]]
# 인덱스 맞추기 위해 0번 인덱스에는 빈배열
1은 자신으로 이미 최적의해가 완성되있습니다. 나머지는 2부터 n 까지 구하는 건데요. n에서 1을 빼는 선택지는 항상 있기 때문에 바로 이전의 해에서 현재 숫자를 더해줄 수 있습니다.
for i in range(2, n+1):
dp.append(dp[i-1]+[i])
# n=2, i=2
# dp: [[], [1]]
# append 이후 dp: [[], [1], [1, 2]]
이후에 나누는 선택지도 진행합니다. 히스토리의 길이(이동회수)를 비교해서 판단합니다.
for i in range(2, n+1):
dp.append(dp[i-1]+[i])
if i%3 == 0 and len(dp[i]) > len(dp[i//3])+1:
dp[i] = dp[i//3] + [i]
if i%2 == 0 and len(dp[i]) > len(dp[i//2])+1:
dp[i] = dp[i//2] + [i]
# n=3, i=3
# append 이후 dp: [[], [1], [1, 2], [1, 2, 3]]
# i%3 조건문 이후 dp: [[], [1], [1, 2], [1, 3]]
전체코드
n = int(input())
dp = [[], [1]]
for i in range(2, n+1):
dp.append(dp[i-1]+[i])
if i%3 == 0 and len(dp[i]) > len(dp[i//3])+1:
dp[i] = dp[i//3] + [i]
if i%2 == 0 and len(dp[i]) > len(dp[i//2])+1:
dp[i] = dp[i//2] + [i]
answer = list(map(str, reversed(dp[n])))
print(len(answer) - 1)
print(" ".join(answer))