눈금 맞추기
문제
실험실의 신호 발생기에는 다이얼이 하나 달려 있고, 다이얼에는 0번부터 100,000번까지 눈금이 매겨져 있다. 지금 다이얼은 N번 눈금에 맞춰져 있고, 실험을 하려면 K번 눈금에 맞춰야 한다.
다이얼을 움직이는 방법은 세 가지뿐이다. 지금 눈금이 X번이라고 할 때 각 방법으로 옮겨 가는 자리는 다음의 표와 같다.
| 방법 | 1 내리기 | 1 올리기 | 두 배 |
|---|---|---|---|
| 옮겨 가는 눈금 | X-1 | X+1 | 2X |
어느 방법이든 한 번 움직이는 데 1초가 걸린다. 세 방법 모두 0번보다 작은 눈금이나 100,000번보다 큰 눈금으로는 갈 수 없다. 그런 자리로 가게 되는 움직임은 쓸 수 없는 것으로 본다. 한 번 지나간 눈금을 다시 지나가도 되고, 목표 눈금을 지나쳤다가 되돌아와도 된다.
N번 눈금에서 K번 눈금으로 맞추기 위해 걸리는 시간의 최솟값을 계산하는 프로그램을 작성하여라.
예를 들어 N=5이고 K=17이라고 해보자. 이때 다음과 같이 네 번 움직이면 17번 눈금에 도달한다.
| 시각 | 0초 | 1초 | 2초 | 3초 | 4초 |
|---|---|---|---|---|---|
| 쓴 방법 | 없음 | 1 내리기 | 두 배 | 두 배 | 1 올리기 |
| 눈금 | 5 | 4 | 8 | 16 | 17 |
5번에서 곧바로 두 배로 가면 10번이고, 거기서 1을 올려 11번, 다시 두 배로 가면 22번이 되어 17번을 지나쳐 버린다. 그 뒤로 1씩 내리면 다섯 번을 더 써야 한다. 세 번 이하로 움직여서 17번 눈금에 도달하는 방법은 없다. 따라서 이 예시에서의 정답은 4초다.
입출력 예시
예시 1
입력
5 17
출력
4
예시 2
입력
1 1
출력
0
예시 3
입력
1 3
출력
2
입력 조건
가장 먼저 지금 다이얼이 맞춰진 눈금 N과 맞춰야 하는 눈금 K가 한 줄에 공백으로 구분되어 주어진다. N과 K는 각각 1 이상 100,000 이하의 자연수다. N과 K가 서로 같을 수도 있다. 다이얼이 지나갈 수 있는 눈금은 0번 이상 100,000번 이하이므로, 중간에 0번 눈금을 지나가는 것은 가능하다. 입력은 이 한 줄로 끝난다.
출력 조건
N번 눈금에서 K번 눈금으로 맞추기 위해 걸리는 시간의 최솟값을 초 단위의 수로 한 줄에 출력한다. 이미 K번 눈금에 맞춰져 있어서 움직일 필요가 없다면 0을 출력한다.
요구사항
- 한 번의 움직임으로 눈금을 1 내리거나 1 올리거나 두 배로 올릴 수 있습니다
- 어느 방법이든 한 번에 1초가 걸립니다
- 0번보다 작은 눈금이나 100,000번보다 큰 눈금으로는 갈 수 없습니다
- 걸리는 시간의 최솟값 하나만 출력합니다
- 표준 입력으로 읽고 표준 출력으로 내보내는 프로그램을 짜야 합니다
- 쓸 수 있는 말은 파이썬, 자바스크립트입니다
- 메모리 제한은 256MB입니다. 브라우저에서는 재지 않고 적기만 합니다
- 시간 제한은 출제자의 정답 코드를 같은 런타임에서 재서 정합니다
- 이 문제는 프롬프트가 아니라 코드를 냅니다. 그 코드는 이 기기의 브라우저에서 돌고, 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다. 실행 시간은 각자 기기가 적어 보내는 값이라, 코드와 기기 정보를 순위표에 같이 내걸어 둡니다.
- 출력이 글자 하나까지 기대값과 같아야 합니다. 줄 안의 빈칸은 다른 글자와 똑같이 봅니다.
- 케이스는 15개이고, 그 가운데 3개는 입력과 기대 출력을 함께 보여 줍니다. 나머지는 제출할 때만 쓰이고 화면에는 보여 주지 않습니다.
- 케이스 15개를 전부 통과해야 해결입니다.
예시
공개 케이스 3개입니다. 채점에는 숨은 케이스가 함께 쓰입니다. 케이스 15개를 전부 통과해야 해결입니다.
5 17
4
1 1
0
1 3
2
풀이
코드는 이 기기에서돕니다. 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다.
제출은 로그인 하셔야 됩니다. 공개 케이스로 돌려보는 것은 로그인 없이도 됩니다.
공개 케이스 3개로 돌려보기가 됩니다. 제출하면 숨은 케이스까지 돕니다.
이 문제를 푼 사람
아직 없습니다. 첫 번째가 되실 수 있습니다.