백준 16953 A -> B 자바 풀이

난이도 : 실버2
풀이일 : 2401217
https://www.acmicpc.net/problem/16953

16953번: A → B

---

링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐

---

풀이 코드

import java.util.Scanner;

public class Main {
	static long A;
	static long B;
	static boolean flag = false;
	
	static void DFS(long s, int count) {
		if (s < B) {
			long next1 = s * 2;
			String temp = Long.toString(s) + "1";
			long next2 = Long.parseLong(temp);
			
			if (next1 == B || next2 == B) {
				System.out.println(count + 1);
				flag = true;
				return;
			}
			else {
				DFS(next1, count + 1);
				DFS(next2, count + 1);
			}
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		A = sc.nextLong();
		B = sc.nextLong();
		
		DFS(A, 1);
		
		if (!flag) {
			System.out.println(-1);			
		}
	}
}

• int로는 감당할 수 없는 긴 숫자가 주어질까봐 long 자료형 사용
• flag : A 숫자 B로 변환 성공 여부 확인
• DFS 재귀 방식 탐색
  • 현재 숫자가 B를 넘어서는 경우, B가 될 수 없으므로, 너무 많은 재귀 호출 방지용 if문 조건 추가
  • 현재 숫자에서 두 가지 변환 방법 시도
  • 시도 후 B가 되었다면 count + 1 출력 후 리턴
  • 시도 후 B가 되지 못했다면 해당 숫자, count + 1 을 넣어 재탐색
• flag가 false라면 -1 출력

---

느낀점

• 처음에는 익숙한 BFS 방식을 사용해서 풀려고 했는데, 문제 조건에서 B가 너무 큰 수로 주어질 수도 있는 것을 확인하고 DFS 방식으로 바꿨다. 어떤 문제를 많이 풀어서 손에 익게 되면 그 방식으로만 문제를 풀려고 일단 시도하는 것 같아서 반성했다.
• 그리고 지금 보니까 옛날이랑 다르게 주석을 안달아두네 싶어서, 이제부터는 푸는 문제들에 주석도 성실히 달아서 커밋해야지.