[➕ 오답노트] 백준 1697번

👇🏻 문제

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

1697번: 숨바꼭질

---

메모리 초과가 난 문제, 메모리를 정해 큐와 시간 배열을 함께 사용하는 문제

나는 이렇게 두 가지 자료구조를 한 번에 사용하는 데에 머리가 안 돌아가는 것 같다.

굳이? 라는 느낌이 들면 무조건 _ _ _ 초과가 뜬다.

인터넷에 널려있는 정답 코드지만 이유가 있겠지...

 

자료형의 크기에 주의하자.

 

import sys
from collections import deque

N, K = map(int, sys.stdin.readline().strip().split())

MAX = 100000
cnt = [0] * (MAX + 1)

q = deque()
q.append(N)

while q:
    x = q.popleft()
    if x == K:
        print(cnt[x])
        break
    for dx in (x+1, x-1, x*2):
        if 0 <= dx < MAX+1 and cnt[dx] == 0:
            cnt[dx] = cnt[x] + 1
            q.append(dx)