반응형
🔗 16953번 A -> B
https://www.acmicpc.net/problem/16953
문제
정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.
- 2를 곱한다.
- 1을 수의 가장 오른쪽에 추가한다.
A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.
입력
첫째 줄에 A, B (1 ≤ A < B ≤ 10^9)가 주어진다.
출력
A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.
📝 접근 방법 및 풀이
처음에는 A를 B로 바꾸는 방식으로 하려 했지만, 거꾸로 B를 A로 바꾸는 로직이 더 빠를 것 같아서 그렇게 해보았습니다.
- B가 2로 나누어 떨어지면,
- B를 2로 나눈다.
- 횟수 += 1
- B의 끝자리가 1이면,
- 1을 제거한다.
- 횟수 += 1
- 나머지 경우는 -1 출력 후 종료
💻 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int A = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
int answer = 1;
while (B != A) {
if( B < A ) {
System.out.println(-1);
return;
}
String str = String.valueOf(B);
if(B % 2 == 0) {
B /= 2;
} else if(str.charAt(str.length() - 1) == '1') {
str = str.substring(0, str.length() - 1);
B = Integer.parseInt(str);
} else {
System.out.println(-1);
return;
}
answer++;
}
System.out.println(answer);
}
}
반응형