수직선 위 시작점 x와 목표 y가 주어질 때, 두 배씩 늘어나는 지그재그 탐색을 따라 y에 도달할 때까지 이동한 총 거리를 구한다.
쉬움3수학시뮬레이션면접 대비아직 제출이 없습니다시간 제한2초메모리 제한512 MB농부 존이 아끼는 소 베시를 잃어버려서 찾아 나서야 한다!
다행히 농장을 가로지르는 길은 긴 길 하나뿐이고, 존은 베시가 이 길 위 어딘가에 있다는 것을 알고 있다. 길을 수직선으로 생각하면 존은 지금 위치 x에 있고 베시는 위치 y에 있다(존은 y를 모른다). 베시의 위치를 안다면 존은 곧장 걸어가서 ∣x−y∣만큼만 이동하면 된다. 하지만 밖이 어두워서 존은 아무것도 볼 수 없다. 존이 베시를 찾는 방법은 앞뒤로 오가다가 결국 베시의 위치에 도달하는 것뿐이다.
앞뒤로 오가는 가장 좋은 전략을 알아내려고 존은 컴퓨터 과학 연구 문헌을 찾아보았다. 그리고 바로 이 문제를 예전에 컴퓨터 과학자들이 연구했고, 이름도 "잃어버린 소 문제(Lost Cow Problem)"라는 사실을 알고 조금 재미있어했다(실제로 있는 문제다!).
문헌이 권하는 방법은 다음과 같다. 먼저 위치 x+1로 이동하고, 방향을 바꿔 위치 x−2로 이동하고, 다시 위치 x+4로 이동하는 식으로 "지그재그"로 움직인다. 매번 처음 출발한 위치에서 직전보다 두 배 먼 곳까지 간다. 존이 공부하면서 읽은 바에 따르면 이 방법으로는 베시를 찾을 때까지 이동하는 거리가 최악의 경우에도 직선 거리 ∣x−y∣의 9배를 넘지 않는다(이것도 사실이며, 9배는 어떤 전략으로도 더 낮출 수 없는 최악의 경우 보장값이다).
존은 이 결과를 직접 확인해 보고 싶다. x와 y가 주어질 때, 위의 지그재그 탐색 전략을 따라 베시를 찾을 때까지 존이 이동하는 전체 거리를 구하시오. 존은 위치 y에 처음 도달하는 순간 멈춘다.
첫째 줄에 서로 다른 두 정수 x와 y가 공백으로 구분되어 주어진다. 두 수는 모두 0 이상 1000 이하이다.
존이 베시에게 도달할 때까지 이동한 거리를 한 줄에 출력한다.