백준 1463 1로 만들기 파이썬 풀이

난이도 : 실버3

풀이일 : 05011

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

1463번: 1로 만들기

---

링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐

---

풀이 코드

# 방문 여부 확인 배열 생성
# 각 숫자를 인덱스로 활용
# 3,2로 나누어 떨어지는 수, 몫 기록
# 숫자 방문 시, 현재까지의 변환 횟수 기록
# 처음 1부터 시작 -> 출력시 -1

import sys
from collections import deque

N = int(sys.stdin.readline().strip())
visited = [0] * (N + 1)

queue = deque([N])
visited[N] = 1
while queue:
    x = queue.popleft()
    # 1 도착 시 visited[1]-1 출력  
    if x == 1:
        print(visited[1]-1)
        break
    # 3으로 나누어 떨어지고, 3으로 나눈 몫 미방문 시 처리
    if not x % 3 and not visited[x//3]:
        queue.append(x//3)
        visited[x//3] = visited[x] + 1
    # 2로 나누어 떨어지고, 2로 나눈 몫 미방문 시 처리
    if not x % 2 and not visited[x//2]:
        queue.append(x//2)
        visited[x//2] = visited[x] + 1
    # 1을 뺀 숫자 미방문 시 처리
    if not visited[x-1]:
        queue.append(x-1)
        visited[x-1] = visited[x] + 1

코드 구성

• 시간 초과 방지를 위한 deque 사용
• 각 숫자를 거쳐갔는지 확인 하기 위한 배열 생성
• 변환하여 거쳐간 숫자는 배열의 해당 숫자 인덱스로 방문 표시
• 3, 2로 나누어 떨어지는 경우를 각각 처리해주고 -1 숫자 처리 -> 나누기가 큰 폭으로 이동 가능
• 숫자 방문 시, 현재까지의 변환 횟수 기록 visited[nx] = visited[x] + 1
• 처음 방문 표시가 1에서 시작되었으므로 출력 시 -1

---

느낀점

얼마 전에 풀었던 숨바꼭질 문제들과 같은 로직이었다.

처음에는 3으로 나누어 떨어지는 경우에 x/3을 deque에 넣으려고 했으나, 자꾸 파이참이 안된다고 해서 프린트를 해보니까 나누어 떨어지더라고 float 형식으로 들어가서 그런거였다.

파이썬 처음 배울때나 신경 썼던 것 같아서 앞으로는 나눌 때 형식 신경쓰기 기억해야지