[BOJ] 17071번: 숨바꼭질 5

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

맨 처음에는 매 초마다 방문 가능한 지점들을 가져가는 $O(500000\sqrt{500000})$ 풀이로 통과했는데, 다른 정답자들의 풀이를 보면서 $O(500000)$ 풀이를 깨달았습니다. +1, -1을 이용하면 2초 후에 제자리로 돌아오는 것이 가능하기에 각 지점은 짝수/홀수 시간에 한 번씩만 방문하면 됩니다. 즉 dist[2][500001] 배열에 한 번씩만 방문하면 되는 것입니다.

https://github.com/blisstoner/BOJ/blob/master/17071.cpp