계수기로 수 만들기
문제
어느 과학관에는 수를 하나 보여 주는 계수기가 놓여 있다. 계수기에는 버튼이 두 개 있고, 버튼을 누르면 화면의 수가 다음과 같이 바뀐다.
| 버튼 | 바뀌는 방식 | 화면이 23일 때 |
|---|---|---|
| 왼쪽 | 화면의 수가 두 배가 된다 | 46 |
| 오른쪽 | 화면의 수 오른쪽에 1이 하나 붙는다 | 231 |
지금 화면에는 수 A가 떠 있다. 버튼을 눌러 화면을 수 B로 만들려고 한다. 이때 화면을 거쳐 간 수가 몇 개인지 세는데, 처음에 떠 있던 A와 마지막에 만든 B도 함께 센다. 버튼을 한 번 누를 때마다 화면에 수가 하나 더 떠오르므로, 거쳐 간 수의 개수는 버튼을 누른 횟수보다 하나 더 많다.
예를 들어 A=2이고 B=162라고 해보자. 버튼을 다음과 같이 네 번 누르면 162를 만들 수 있다.
| 누른 버튼 | 처음 | 왼쪽 | 왼쪽 | 오른쪽 | 왼쪽 |
|---|---|---|---|---|---|
| 화면의 수 | 2 | 4 | 8 | 81 | 162 |
화면을 거쳐 간 수는 2, 4, 8, 81, 162의 다섯 개다. 이보다 적게 눌러 162를 만드는 방법은 없으므로 이 경우의 답은 5다.
A와 B가 같으면 버튼을 한 번도 누르지 않는다. 이때 화면을 거쳐 간 수는 처음의 A 하나뿐이므로 답은 1이다.
B를 만들 수 없는 경우도 있다. A=2이고 B=3이라면 왼쪽 버튼을 눌러 4가 되거나 오른쪽 버튼을 눌러 21이 되는데, 둘 다 3을 지나친다. 화면의 수는 버튼을 누를 때마다 커지기만 하므로 되돌릴 수도 없다. 이런 경우에는 -1을 답으로 한다.
B에서 거꾸로 거슬러 올라가는 방법도 있다. B가 짝수이면 두 배가 되기 전의 수는 B를 2로 나눈 값이고, B의 일의 자리가 1이면 1이 붙기 전의 수는 B에서 일의 자리를 떼어 낸 값이다. B=162에서 거슬러 올라가면 다음과 같다.
| 단계 | 화면의 수 | 거슬러 올라간 방식 |
|---|---|---|
| 1 | 162 | 처음 |
| 2 | 81 | 짝수라 2로 나눴다 |
| 3 | 8 | 일의 자리가 1이라 떼어 냈다 |
| 4 | 4 | 짝수라 2로 나눴다 |
| 5 | 2 | 짝수라 2로 나눴다 |
이렇게 A에 닿으면 그때까지 거친 수의 개수가 답이 된다. 짝수도 아니고 일의 자리가 1도 아닌 수에 걸리거나 A보다 작아지면 B를 만들 수 없다.
A와 B가 주어졌을 때, 버튼을 가장 적게 눌러 B를 만들었을 때 화면을 거쳐 간 수가 몇 개인지 구하는 프로그램을 작성하여라. B를 만들 수 없으면 -1을 구한다.
입출력 예시
예시 1
입력
2 162
출력
5
예시 2
입력
1 1
출력
1
예시 3
입력
2 3
출력
-1
입력 조건
첫째 줄에 처음 화면에 떠 있는 수 A와 만들어야 하는 수 B가 공백 하나로 구분되어 주어진다. A와 B는 모두 1 이상 1,000,000,000 이하의 자연수다. 이때 A는 B보다 작거나 같다.
입력은 이 한 줄로 끝난다. 버튼을 누를 수 있는 횟수에는 제한이 없다. A와 B가 같은 경우도 주어진다.
출력 조건
버튼을 가장 적게 눌러 B를 만들었을 때 화면을 거쳐 간 수의 개수를 첫째 줄에 출력한다. B를 만들 수 없으면 -1을 출력한다.
수 하나를 출력하고 줄을 바꾼다. 앞뒤에 다른 글자나 공백은 붙이지 않는다.
요구사항
- 입력은 표준 입력으로 받고 답은 표준 출력으로 내보냅니다
- 세는 값은 버튼을 누른 횟수가 아니라 화면을 거쳐 간 수의 개수입니다. 처음의 A와 마지막의 B를 모두 셉니다. 그래서 답은 버튼을 누른 횟수보다 하나 더 큽니다
- A와 B가 같으면 버튼을 한 번도 누르지 않으므로 답은 1입니다
- 오른쪽 버튼은 수 오른쪽에 1을 붙입니다. 1을 더하는 것이 아닙니다
- B를 만들 수 없으면 -1을 출력합니다
- 채점은 출력을 기대값과 글자 하나까지 견줍니다
- 표준 입력으로 읽고 표준 출력으로 내보내는 프로그램을 짜야 합니다
- 쓸 수 있는 말은 파이썬, 자바스크립트입니다
- 메모리 제한은 256MB입니다. 브라우저에서는 재지 않고 적기만 합니다
- 시간 제한은 출제자의 정답 코드를 같은 런타임에서 재서 정합니다
- 이 문제는 프롬프트가 아니라 코드를 냅니다. 그 코드는 이 기기의 브라우저에서 돌고, 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다. 실행 시간은 각자 기기가 적어 보내는 값이라, 코드와 기기 정보를 순위표에 같이 내걸어 둡니다.
- 케이스는 15개이고, 그 가운데 3개는 입력과 기대 출력을 함께 보여 줍니다. 나머지는 제출할 때만 쓰이고 화면에는 보여 주지 않습니다.
- 케이스 15개를 전부 통과해야 해결입니다.
예시
공개 케이스 3개입니다. 채점에는 숨은 케이스가 함께 쓰입니다. 케이스 15개를 전부 통과해야 해결입니다.
2 162
5
1 1
1
2 3
-1
풀이
코드는 이 기기에서돕니다. 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다.
제출은 로그인 하셔야 됩니다. 공개 케이스로 돌려보는 것은 로그인 없이도 됩니다.
공개 케이스 3개로 돌려보기가 됩니다. 제출하면 숨은 케이스까지 돕니다.
이 문제를 푼 사람
아직 없습니다. 첫 번째가 되실 수 있습니다.