시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 652 174 148 34.742%

문제

현욱은 옛날 자신에게 알고리즘을 가르쳐 준 스승님이 어느 신비로운 밀림 속 나무 아래에서 수행 중이라는 사실을 전해 들었다.

이 무한한 넓이의 밀림에는 모든 격자점(x, y 좌표가 모두 정수인 위치)마다 완전히 똑같은 모양의 나무가 한 그루씩 심어져 있고, 현욱의 스승은 그 중 (M,N) 좌표의 나무 아래에서 수행을 하고 있다.

이 밀림에는 또 다른 특징이 있는데, 어떤 나무 아래에서 볼 수 있는 다른 나무로 순간이동을 할 수 있다는 것이다. 어떤 나무 아래에서 다른 나무를 보려면, 그 두 나무의 좌표를 잇는 직선을 그었을 때 중간에 다른 나무가 존재하지 않아야 한다. 

예를 들어, 현욱이 (0, 0) 위치에 있을 때 (1, 1) 위치에 있는 나무 혹은 (1,2) 위치에 있는 나무는 볼 수 있기 때문에 바로 순간이동 할 수 있다. 하지만 (2, 4) 위치에 있는 나무는 (1, 2) 위치에 있는 나무에 가려 보이지 않으므로 바로 순간이동 할 수 없다.

현욱은 수행을 돕기 위해 스승님이 있는 곳으로 가려고 한다. 하지만 밀림의 신비로운 기운으로 인해 나무 사이를 걸어서 이동하는 것은 위험할 수 있어서, 현욱은 순간이동만 이용해서 (M, N) 위치로 이동할 것이다. 또, 순간이동은 할 때마다 멀미가 심하게 나기 때문에 현욱은 최대한 적은 횟수만큼만 순간이동을 사용해서 (M, N) 위치로 이동하려고 한다.

이 밀림에 들어오는 모든 사람은 저절로 (0,0) 위치에 있는 나무 밑으로 이동하게 된다. 현욱을 도와 (0,0) 위치의 나무 아래에서 (M, N) 위치의 나무 아래로 이동하는 데 필요한 최소 순간이동 횟수를 구해보자.

입력

첫째 줄에 현욱의 스승이 있는 위치를 나타내는 두 정수 M, N이 주어진다.

출력

첫째 줄에 (M, N) 좌표로 이동하기 위해 필요한 최소 순간이동 횟수를 출력한다.

제한

  • -109 ≤ M,N ≤ 109

서브태스크 1 (1점)

  •  NM은 동일하다.

서브태스크 2 (2점)

  • 추가 제한 없음

예제 입력 1

2 4

예제 출력 1

2

출처

Contest > 소프트콘 > 제2회 소프트콘 A번

채점

  • 예제는 채점하지 않는다.