16953번: A → B
첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.
www.acmicpc.net
의식의 흐름
A에서 B로 가면 경우의 수가 너무 많을 것 같으니까 B에서 A로 가볼까..?
일의 자리가 1이거나 짝수일 때만 연산 가능하니까 그 경우만 처리해주고 나머지는 -1이겠지!
풀이
B를 A로 만들기 도전
1. B의 일의 자리가 1인 경우 1을 없애주고, B가 짝수인 경우 2로 나누어준다.
만약, 2가지 경우 중 하나에 포함되지 않는 경우(ex. 일의 자리가 3인 경우)는 A로 만들지 못하는 경우이므로 -1 출력
2. 1번 연산을 B<A 또는 B==A일 때까지 반복한다.
코드
import java.io.*;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
long A = Long.parseLong(st.nextToken());
long B = Long.parseLong(st.nextToken());
int cnt = 1;
while(true){
if(B%10==1) // 일의 자리가 1인 경우
B = (B-1)/10;
else if(B%2==0) // 짝수인 경우
B /= 2;
else {
bw.write("-1");
break;
}
cnt++;
if(B<A){ // 만들 수 없는 경우
bw.write("-1");
break;
}
else if(B==A){ // 만든 경우
bw.write(Integer.toString(cnt));
break;
}
}
bw.flush();
}
}
'알고리즘 > 백준' 카테고리의 다른 글
[JAVA] 백준 q11003 - 최솟값 찾기 (0) | 2023.08.08 |
---|---|
[JAVA] 백준 q17276 - 배열 돌리기 (0) | 2023.06.22 |
[JAVA] 백준 q1253 - 좋다 (1) | 2023.06.10 |
[JAVA] 백준 q11659 - 구간 합 구하기 4 (0) | 2023.06.10 |
[JAVA] 백준 q1072 - 게임 (0) | 2023.05.01 |