[6] 나잡아봐라~

<나잡아봐라>

[문제 설명]

연인 코니와 브라운은 광활한 들판에서 '나 잡아 봐라' 게임을 한다. 이 게임

은 브라운이 코니를 잡거나 코니가 너무 멀리 달아나면 끝난다. 게임이 끝나

는데 걸리는 최소 시간을 구하시오.

[조건]

코니는 처음 위치에서 1초 후 1만큼 움직이고, 이 후에는 가속이 붙어 매 초

마다 이전 이동 거리 + 1 만큼 움직인다. 즉, 시간에 따른 코니의 위치는 C, 

C + 1, C + 3, C + 6, ...이다.

브라운은 현재 위치 B에서 다음 순간 B - 1, B + 1, 2 * B 중 하나로 이동할 

수 있다.

코니와 브라운의 위치 x는 0 <= x <= 200,000이다.

브라운은 범위를 벗어나는 위치로는 이동할 수 없고, 코니가 범위를 벗어나

면 게임이 끝난다.

[입출력]

*입력 형식

표준 입력의 첫 줄에서 코니의 위치 C와 브라운의 위치 B를 공백으로 구분하

여 순서대로 읽는다.

*출력 형식

브라운이 코니를 잡을 수 있는 최소 시간 N초의 N을 표준 출력에 쓴다.

브라운이 코니를 잡지 못한 상태로 게임이 끝나면 표준 출력에 -1을 쓴다.

(예)

입력: 11 2

출력: 5

==> 코니의 위치: 11, 12, 14, 17, 21, 26, ...

==> 브라운의 위치: 2, 3, 6, 12, 13, 26, ...

브라운은 코니를 5초 만에 잡을 수 있다.

===============================================

1) 분석

: 코니는 재귀로 금방 구할수 있다. 문제는 브라운인데.. 자꾸 DFS로만 풀었

다....

디버깅하려고 숫자를 찍어봤는데 답이없었다.. 누가봐도 시간터짐....

bfs로 푸니까 금방풀렸다.. 생각해보면 DFS는 TREE에서 한 TESTCASE에 대해

서 계속 파고들고 그 Depth가 끝나면 그다음 case로 이동함

그러면 만약에 dept

h가 세자리수를 넘는다 그러면 당연히 시간이 터질수 밖

에없다... 그런데 bfs는 depth별로 모든 경우의 수를 뚫고 지나

간다. 당연히 이방법으로 풀었어야하는데 왜 dfs를 고집했는지 모르겠다... 

 

2) Codes