이 문제의 핵심적인 스포일러입니다. 스포일러를 원하지 않으시는 분은 뒤로가기를 눌러주세요.
*** 스포일러 ***
어떤 점 x에 t초에 도달할 수 있다면, t+2, t+4, t+6, ... 에도 x에 도달할 수 있습니다. 좌우로 한 번 왔다갔다하면 다시 제자리로 돌아오기 때문입니다. 즉, 짝수초에 x에 도달하는 최단 시간과 홀수초에 x에 도달하는 최단거리를 각각 구하면 됩니다.
17071번 - 숨바꼭질 5
2번 접근 방법의 경우 동생이 움직이는 시간은 최대 약 700초이기 때문에, 700초마다 최대 50만 개의 점을 set에 담고 contains로 찾는 것은 O(1) 접근 시간을 가지는 HashSet을 가정해도 3억 5천으로 시간 내에 통과할 수 없습니다.
3번 접근 방법 역시 정렬하는 데에 50만log50만을 700번 반복해야 하기 때문에 더 느립니다.
홀수초와 짝수초를 나누는 것의 의미는 예를 들어 홀수초를 저장하는 visited에 7이라는 값이 이미 들어가있다면 이후 홀수초에서 7을 방문할 수 있다고 하더라도 7을 큐에 넣지 않는다는 의미입니다. 그래서 50만 개의 점은 각각 많아야 2번씩 큐에 들어가고(홀수초일 때 한 번, 짝수초일 때 한 번) 많아야 100만개의 정점만을 탐색하게 됩니다.
댓글을 작성하려면 로그인해야 합니다.
yih9329 5년 전 2
2. 단위시간마다 동생의 위치를 업데이트하고, 시간이 지나기 전에 수빈이가 위치할 수 있는 모든 공간을 set에 저장해뒀습니다. 동생의 위치가 다음턴에 x라고 하면 잡힐 수 있는 경우는 수빈이가 x-1, x+1, 2x에 있을 때 뿐이므로 set자료구조의 contains를 이용하여 셋 중에 해당되는 값이 있는지를 확인했습니다. 하지만 이 경우에는 시간초과가 나서 이 방법또한 접었습니다.
3. 2번의 방법과 비슷하게 시도했는데 set자료구조를 사용하지 않고 list에 수빈이의 위치를 저장해두고 정렬을 한 후, 이진탐색으로 x-1, x+1, 2x에 해당하는 값이 있는지 확인했습니다. 2번의 경우와 비교해서 속도가 근소하게 빨라지긴했으나 여전히 시간초과가 납니다.
제 머리로는 더이상 어떤 방법을 써야될지 모르겠습니다.ㅠㅠ
시간초과가 나지 않으려면 어떤식으로 접근해야할까요? 도움부탁드립니다.