[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

'알고리즘 > BOJ' 카테고리의 다른 글

[BOJ] 12851번: 숨바꼭질 2  (0) 2019.03.29
[BOJ] 16440번: 제이크와 케이크  (0) 2019.03.22
[BOJ] 13549번: 숨바꼭질 3  (0) 2019.03.22
[BOJ] 16936번: 나3곱2  (0) 2019.03.15
[BOJ] 17069번: 파이프 옮기기 2  (0) 2019.03.15
[BOJ] 11967번: Switching on the Lights  (2) 2019.03.10
  Comments