mingssssss

1. 문제

https://www.acmicpc.net/submit/16953/42924302

2. 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

	// 전역 변수 설정(*int로 할당하면 오버플로우 발생)

	static long a, b;
	static long N, M;
	static long size;
	static long cnt;

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Scanner sc = new Scanner(System.in);

		N = Long.parseLong(sc.next());
		M = Long.parseLong(sc.next());

		Queue<Long> q = new LinkedList<>();

		// 시작 숫자 추가
		q.add(N);

		while (!q.isEmpty()) {
			
			// *Queue의 길이를 구해서 한 차수씩 탐색
			size = q.size();

			for (int i = 0; i < size; i++) {

				long temp = q.poll();

				if (temp == M) {
					System.out.println(cnt + 1);
					return;
				}

				if (temp * 2 <= M) {
					q.add(temp * 2);
				}

				if ((temp * 10) + 1 <= M) {
					q.add((temp * 10) + 1);
				}
			}
			// 한 차수가 끝나면 cnt++
			cnt++;
		}

		// 숫자를 만들 수 없는 경우
		System.out.println(-1);

	}

}

3. 리뷰

옛날 부터 꼭 풀고싶었던 타겟 넘버 찾기 문제이다.

BFS 동작 방식을 이해하고 나서는 풀이법을 어렴풋이 알게됐다.

처음에는 타겟넘버의 숫자만큼 배열을 만들어서 탐색하는 알고리즘을 짰다.

답은 맞지만, 입력 최댓값이 (1 ≤ A < B ≤ 10^^9) 이여서 메모리 초과가 났다.

ArrayList등으로도 푸려고 했으나, 근본적인 문제가 해결이 되지 않았다.

구글링을 통해 배열을 이용하지 않고 푸는 방법을 검색했다.

한 차수가 넘어갈 때마다 cnt++를 해주면 배열을 만들지 않고도 cnt체크가 가능했다.

for문 진입 전에 Queue의 size를 구해서 한 차수마다 cnt++를 해줬다.

이렇게 되면 *2 연산과 숫자의 맨 끝에 1을 더하는 계산이 끝나고 cnt++를 해줘서

타겟 넘버까지의 거리를 계산할 수 있게 되었다.

항상 궁금했던 부분인데 해결이 되어서 다행이다.

또한 int형으로 자료형을 설정하면 입력값이 큰 경우 오버플로우가 발생해서

Long으로 선언해줬다. 항상 입.출력값을 잘 확인하는 습관을 들여야겠다.