백준 16953번
https://www.acmicpc.net/problem/16953
정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.
A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.
첫째 줄에 A, B (1 ≤ A < B ≤ 10)가 주어진다.
A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.
2 162
2 → 4 → 8 → 81 → 162
4 42
100 40021
100 → 200 → 2001 → 4002 → 40021
5
-1
5
DFS/BFS와 Greedy 알고리즘 유형의 문제입니다.
조건만 이해를 한다면, 충분히 풀 수 있는 문제였습니다.
조건은 문제에 모두 명시되어 있습니다.
A라는 숫자를 B로 만드는데
가장 뒤에 1을 붙이거나, 2를 곱해서 B로 만드는 것,
저는 반대로 풀었습니다.
A -> B 로 가는 것이 문제였지만, 보통 미로를 풀 때도 출발점에서 도착점으로 가는 건 어렵지만 도착점에서 출발점으로 가는 건 쉽습니다.
이런 것처럼 이 문제도 B -> A로 반대로 가면 조금 더 쉽게 풀 수 있을 것으로 생각했습니다.
그래서 B
와 A
가 같지 않으면 계속 반복되도록 했고,
탈출 조건은 A
==B
이면 자동 탈출이고, 예외로는 B
보다 A
가 커질 경우,
즉 B
가 A
를 지나칠 경우입니다.
이 경우는 당연히 A
와 B
는 다르다니까 count = -1
로 break 해주면 됩니다.
각 조건은
B
가 짝수일 경우 2로 나누어주고,
가장 뒤의 숫자가 1일 경우 1을 제거
B
가 홀수가 될 경우 2로 나눌 수 없으므로 바로 count
= - 1 로 break를 해주면 됩니다.
BFS도 크게 다르지 않습니다. Queue를 사용해서 구현하여
탈출조건을 Greedy알고리즘에서 사용한 조건으로 만들어주면 됩니다.
DFS/BFS문제인데, 왜 자꾸 다른방법으로 풀게되지?
괜찮은건가?
import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); long A = Long.parseLong(st.nextToken()); long B = Long.parseLong(st.nextToken()); int count = 1; while(B != A) { String str = Long.toString(B); if(B % 2 == 0) { B /= 2; } else if(str.charAt(str.length() -1) == '1') { B = Long.parseLong( str.substring(0, str.length() - 1) ); } else { count = -1; break; } if(B < A) { count = -1; break; } count ++; } System.out.println(count); } // End of main } // End of class
import java.util.*; import java.io.*; public class Main { static Queue<Long> que = new LinkedList<>(); static long A, B; static int count = 1; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); A = Long.parseLong(st.nextToken()); B = Long.parseLong(st.nextToken()); BFS(); System.out.println(count); } static void BFS() { que.offer(B); while( !que.isEmpty() ) { long num = que.poll(); String str = Long.toString(num); if(num == A) { return; } else if(num < A) { count = -1; return; } if(num % 2 == 0) { num /= 2; que.offer(num); count ++; } else if(str.charAt(str.length() -1) == '1') { num = Long.parseLong( str.substring(0, str.length() - 1) ); que.offer(num); count ++; } else { count = -1; return; } } } // End of BFS } // End of class