[백준 12852번] 파이썬 - 1로 만들기2

http://www.acmicpc.net/problem/12852

12852번: 1로 만들기 2

 

# 조건

• 정수 X에 사용할 수 있는 연산은 아래와 같은 3가지이다.
  • X가 3으로 나누어 떨어지면, 3으로 나눈다.
  • X가 2로 나누어 떨어지면, 2로 나눈다.
  • 1을 뺀다.
• 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다.
• 연산을 사용하는 횟수의 최솟값을 출력하시오

 

# 접근 방법

• bfs와 deque를 이용해준다.
• 현재 연산 횟수와 현재 수, 연산을 거쳐간 숫자를 같이 넣어준다.
• 1이 될 때까지 반복
• bfs로도 통과했지만 2번째 코드는 dp를 이용한 코드

 

bfs 이용

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from collections import deque  
  
N = int(input())  
visited = [0] * (N+1)  
q = deque()  
q.append((N, [N]))  
while q:  
    num, result = q.popleft()  
    if num == 1:  
        print(len(result) -1)  
        print(*result)  
        break  
    if not visited[num]:  
        visited[num] = 1  
        if not num % 3:  
            q.append((num//3, result+[num//3]))  
  
        if not num % 2:  
            q.append((num//2, result+[num//2]))  
  
        q.append((num-1, result+[num-1]))

 

dp 이용

• history 리스트에 지나온 숫자를 기록해준 후 마지막에 출력해주었다.

n = int(input())  
  
dp = [i for i in range(n + 1)]  
dp[1] = 0  
history = [i for i in range(n + 1)]  
history[1] = 0  
  
for i in range(2, n + 1):  
    dp[i] = dp[i - 1] + 1  
    history[i] = i - 1  
  
    if i % 3 == 0 and dp[i] > dp[i // 3] + 1:  
        dp[i] = dp[i // 3] + 1  
        history[i] = i // 3  
    if i % 2 == 0 and dp[i] > dp[i // 2] + 1:  
        dp[i] = dp[i // 2] + 1  
        history[i] = i // 2  
  
print(dp[n])  
print(n, end=" ")  
  
back_num = n  
while history[back_num] != 0:  
    print(history[back_num], end=" ")  
    back_num = history[back_num]