코테/백준
[BOJ] 16953 A->B (Java)
zsunny
2024. 11. 4. 23:31
https://www.acmicpc.net/problem/16953
A에서 B를 만드는 방법은 여러개이고, 현재 값에서 다음 값으로 갈때 어떤 연산을 해야 더 빠른지 알 수 없다.
하지만 역순으로 생각하면 다르다! B에서 1이 있으면 무조건 1을 더하는 연산을 쓸 수 밖에 없으니 이 연산을 우선순위로 두고 나아가면 된다.
즉, B -> A로 가면서 1이 있으면 1을 제외하고, 1이 없으면 2를 나누고, 두 연산 다 되지 않거나 B의 연산값이 A보다 작아지면 -1을 출력한다.
<제출 코드>
package BOJ.Greedy;
import java.util.Scanner;
public class BOJ_16953_AtoB {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int a = sc.nextInt();
int b = sc.nextInt();
int cnt = 0;
// 1이 있으면 1을 빼주고, 없으면 2로 나눠줌
while(true){
// a가 만들어진 경우
if(b == a) break;
// a로 만들 수 없는 경우
if(b < a) {
cnt = -2;
break;
}
// 1이 있는 경우
String strB = Integer.toString(b);
int len = strB.length();
if(strB.charAt(len-1) == '1') {
cnt++;
strB = strB.substring(0, len-1);
b = Integer.parseInt(strB);
}
// 2로 나누어지는 경우
else if(b % 2 == 0){
cnt++;
b = b / 2;
}
// 두 연산 다 안되는 경우
else {
cnt = -2;
break;
}
}
System.out.println(cnt+1);
}
}