블로그 이사 중입니다 >> gumgood.github.io

13913 숨바꼭질 4 본문

Problem Solving/문제 풀이

13913 숨바꼭질 4

gumgood 2017. 5. 31. 00:05

C++11


X 위치에서 이동할 수 있는 위치는 X-1, X+1, 2*X이다.

각 지점 X를 vertex라 생각하고, 1초간 이동할수 있는 vertex간에 edge로 연결된 graph를 생각하자.

n지점에서 bfs를 돌려서 k지점까지의 최단거리를 찾으면 된다.


각 vertex에 최대 3개의 edge가 연결되므로 O(n)에 가능

역추적도 O(n)에 가능

'Problem Solving > 문제 풀이' 카테고리의 다른 글

11917 이상한 수열  (0) 2017.05.31
13863 Cubes  (0) 2017.05.31
13913 숨바꼭질 4  (0) 2017.05.31
5355 화성 수학  (0) 2017.05.30
7774 콘센트  (0) 2017.05.30
3758 KCPC  (0) 2017.05.30
Tag
0 Comments
댓글쓰기 폼