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

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

12852번: 1로 만들기 2

Problem

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

조건

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

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

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

SOL

순간이동과 비슷한 문제이다. 10^6개의 공간을 나열해놓고, "1"이라는 지점에 도착하는 순간을 봐주면 된다.

이때, 내가 거쳐온 경로를 기록해야하는데, 변수 1개에 값을 담기에는, 한 가지의 경로가 지나온길이 아니라, 여러가지 경로의 지나온 길이 섞일 수 있기 때문에, deque에 같이 경로를 기록하는게 좋아보인다.

 

Trouble Shooting

• lst뒤에 더해줄 때, lst.append()를 사용해줬는데, 이렇게되면, lst가 none이 되버린다.
• 왜냐하면, lst.append()는 append를 실행하는 함수이고, return은 none이기 때문에, none이 반환이 된다.
• 그리고, lst.append(x//3)을 하고, 후에 dq.append(x//3,lst)를 해준다해도, 원래의 lst가 위에서 변질되서 밑으로 내려오기 때문에, 온전한 순서를 유지하기 힘들다.
• 따라서, 리스트 자체를 바꿔서, 완전 새로운 리스트를 그때 그때 넘겨줘야한다.

import sys
from collections import deque
input =sys.stdin.readline

# 그리디 ? no, 완탐

N=int(input().rstrip())
visited=[0 for _ in range(N+1)]

def bfs(x):
    dq=deque()
    dq.append((x,[x]))
    while dq:
        x,lst=dq.popleft()
        #print(x,lst)
        if x==1:
            #연산횟수 
            print(len(lst)-1)
            print(*lst)
            break
        if not visited[x]:
            visited[x] = 1
            if x%3==0:
                dq.append((x//3,lst.append(x//3)))
            if x%2==0:
                dq.append((x//2,lst.append(x//2)))
            dq.append((x-1,lst.append(x-1)))

bfs(N)

수정된 코드

• 수정된 코드에서는 lst의 덧셈기능을 이용해주었다. lst의 덧셈기능은, 서로 더한뒤 새로운 리스트를 반환하게 된다.

import sys
from collections import deque
input =sys.stdin.readline

# 그리디 ? 

N=int(input().rstrip())
visited=[0 for _ in range(N+1)]

def bfs(x):
    dq=deque()
    dq.append((x,[x]))
    while dq:
        x,lst=dq.popleft()
        #print(x,lst)
        if x==1:
            #연산횟수 
            print(len(lst)-1)
            print(*lst)
            break
        if not visited[x]:
            visited[x] = 1
            if x%3==0:
                dq.append((x//3,lst+[x//3]))
            if x%2==0:
                dq.append((x//2,lst+[x//2]))
            dq.append((x-1,lst+[x-1]))

bfs(N)