(Python/🥈1)백준 알고리즘 12852번: 1로 만들기 2

 

문제 바로가기 

1로 만들기 2

문제:

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

입력:

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

 

출력:

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 둘째 줄에는 N을 1로 만드는 방법에 포함되어 있는 수를 공백으로 구분해서 순서대로 출력한다. 정답이 여러 가지인 경우에는 아무거나 출력한다.

 

 

시간초과 코드

 

import sys
from collections import deque

sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')


n = int(input())
q = deque()
q.append([n])
ans = []
while q:
    lst = q.popleft()
    x = lst[0]
    if x == 1:
        ans = lst
        break

    if x % 3 == 0:
        q.append([x // 3] + lst)

    if x % 2 == 0:
        q.append([x // 2] + lst)

    q.append([x - 1] + lst)
ans.reverse()
print(len(ans) - 1)
print(*ans)

 

이 전에 1로 만들기 1 를 풀어서 무시 했는데, 이 문제는 1이 되는 과정을 기억해야한다.

그 기억을 위해서 q를 사용하고 q전체를 가지고 다니는 식으로 했다.

 

q.append 부분이 좀 다른데 이 부분에서

 

if조건을 만족할때 그 다음 숫자를 q에 담아주기 위해 [x//3] + lst를 해준다.

그러면 리스트 [] + [] 이기 때문에 [] 형이 담기기된다. 

 

q = deque()
q.append([n])

이렇게 해주면 리스트 형식으로 들어가기 때문에 popleft를 해주면

[n] 이 나온다.

하지만 q = deque(n) 을 해주고 popleft를 해주면 리스트형으로 빠지지 않는다.

 

하지만 위 코드는 시간초과가 난다.

시간초과를 줄이기위해  sys.stdin 을 사용해주고  pypy3로 제출을 해준다.

 

 

정답 코드 : pypy3 

import sys
from collections import deque

n = int(sys.stdin.readline())
q = deque()
q.append([n])
ans = []
while q:
    lst = q.popleft()
    x = lst[0]
    if x == 1:
        ans = lst
        break

    if x % 3 == 0:
        q.append([x // 3] + lst)

    if x % 2 == 0:
        q.append([x // 2] + lst)

    q.append([x - 1] + lst)
print(len(ans) - 1)
print(*ans[::-1])