[16953번] A -> B ( 탐욕법 )

---

b의 값이 2로 나누어지면 나누고, 안 떨어지면 마지막 1을 지우는데
각 과정에서 계산한 값이 a랑 같으면 그 즉시 cnt를 출력하고 return;
다르면 -1 출력
애초에 2로도 안 나누어 떨어지고 1로도 못 지우면 -1

---

✅ 시간 초과

아래 while문의 시간 복잡도는 O(log b)입니다.

• b가 2의 거듭제곱일 때마다 b를 2로 나누기 때문이다.
• b의 일의 자리가 1일 때마 b를 10으로 나누기 때문에 O(log10 b) 이다.

따라서 전체 시간 복잡도는 대략 O(log b)가 될 수 있는데, 왜 시간초과 인 것일까?

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		int a = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());

		String ss = String.valueOf(b);
		String backSSS = ss.substring(ss.length() - 1);
		int backSS = Integer.parseInt(backSSS);


		int cnt = 0;

		//b의 값이 2로 나누어지면 나누고, 안 떨어지면 마지막 1을 지우는데, 이 단계를 1번씩 걸친 결과값을 저장을 한다. 그래서 그 값이 a랑 같으면 그 즉시
		//cnt를 출력하고 break; 다 했는데도 다르면 -1 출력
		//애초에 2로도 안 나누어 떨어지고 1로도 못 지우면 -1

		if (b % 2 != 0 && backSS != 1) {
			System.out.println(-1);
		}

		while (b > a) {
			if (b % 2 == 0) {
				cnt++;
				b = b / 2;
				if (a == b) {
					System.out.println(cnt + 1);
					return;
				}
			} else {
				String s = String.valueOf(b);
				String frontS = s.substring(0, s.length() - 1);
				String backS = s.substring(s.length() - 1);
				int front = Integer.parseInt(frontS);
				int back = Integer.parseInt(backS);
				if (back == 1) {
					cnt++;
					b = front;
					if (a == b) {
						System.out.println(cnt + 1);
						return;
					}
				}
			}
		}

		System.out.println(-1);

	}
}

이해를 못 했지만, 구현은 완료해야 하니까 풀이를 봤다.
while문을 자유자재로 쓰는 것이 아직은 미숙한 거 같다.
조금 더 연습해보는 게 필요하다.
while문 연습은 탐욕법이 제격인듯

그리고 생각을 말로 한 번 정리하고 구현을 하는 습관을 익혀야 할 거 같다.

---

✅ 코드

charAt을 쓰면 범위가 아닌 특정 문자만 추출할 수 있으니까. subString() 이랑 같이 알아두자.

str.charAt(str.length() - 1);

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		int a = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());

		int cnt = 0;

		while (b != a) {
			if (b < a) {
				System.out.println(-1);
				return;
			}

			String str = String.valueOf(b);

			if (b % 2 == 0) {
				cnt++;
				b /= 2;
				if (a == b) {
					System.out.println(cnt + 1);
					return;
				}
			} else if (str.charAt(str.length() - 1) == '1') {
				cnt++;
				str = str.substring(0, str.length() - 1);
				b = Integer.parseInt(str);

				if (a == b) {
					System.out.println(cnt + 1);
					return;

				}
			} else {
				System.out.println(-1);
				return;
			}
		}

		System.out.println(cnt + 1);

	}
}

---

👾 다른 풀이

논외로 queue를 사용한 풀이도 있다.

만약 5억을 10억으로 만들 경우에는
두 가지 종류의 연산 중 마지막 자리에 1을 붙이는 연산을 진행할 경우에 Queue 에 50억+1 이 들어가야 하므로 overflow가 발생하게 된다!
그래서 int가 아닌 long을 사용해야 하는 거였다.

그래서 long을 쓴다고 한다.

import java.util.*;
import java.io.*;

public class boj16953 {
    static long a,b;
    static int cnt;

    static int bfs(){
        Queue<Long> q = new LinkedList<>();
        q.add(a);

        while(!q.isEmpty()){
            int size = q.size();

            for(int i=0; i<size; i++){
                long tmp = q.poll();
                if(tmp==b)
                    return cnt+1;

                if(tmp*2<=b) q.add(tmp*2);
                if(tmp*10+1<=b) q.add(tmp*10+1);
            }
            cnt++;
        }
        return -1;
    }

    public static void main(String args[]) throws IOException {
        BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(bfr.readLine());

        a = Long.parseLong(stk.nextToken());
        b = Long.parseLong(stk.nextToken());

        System.out.println(bfs());
    }
}

---