[Java] 백준 16953 A -> B - 실버2 (그리디, bfs)

 

https://www.acmicpc.net/problem/16953

16953번: A → B

 

예시 몇 개

1 1

1 2

1 11

 

 

 

그리디 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

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());
    int start = Integer.parseInt(st.nextToken());
    int end = Integer.parseInt(st.nextToken());
    //입력끝 ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

    int result = 0;

    while (end > start) {
      if (end % 2 == 0) {
        end = end/2;
      } else {
        if (end % 10 != 1)
          break;

        end = end/10;
      }

      result += 1;
    }

    if (end != start)
      System.out.println(-1);
    else
      System.out.println(result + 1);

  }
}

다이나믹 프로그래밍으로 풀어야하나 했지만 짝수일 때 홀수일 때 해야하는 일이 딱 정해져있는 걸 보고 그냥 그리디로 풀었다.

• end값이 짝수면 2로 나눠주고, 홀수면 1 값을 빼서 start값으로 만들 수 있는지 없는지만 판별하면 된다
• end값을 조작해서 start값이 될 수 없으면 -1을 출력한다
• 홀수지만 1로 끝나지 않는 값이 계산중에 나올 경우 -1을 출력한다

 

 

 

 

bfs 풀이

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


public class Main {
  public static void main(String[] args) throws IOException {
    //입력 ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    long start = Long.parseLong(st.nextToken());
    long end = Long.parseLong(st.nextToken());

    //bfs를 사용하면 최소 연산횟수를 구할 수 있다!
    Queue<List<Long>> queue = new LinkedList<>();
    List<Long> tmp = new ArrayList<>();
    tmp.add(start);tmp.add(0L);
    queue.add(tmp);

    if (start == end) {
      System.out.println(0);
      return;
    }

    Long result = -1L;

    while (!queue.isEmpty()) {
      List<Long> list = queue.poll();
      long value = list.get(0);
      long moveCnt = list.get(1);

      if (value * 2 == end || value*10 + 1 == end) {
        result = moveCnt+1;
        break;
      }

      //곱하기 2
      if (value * 2 < end) {
        tmp = new ArrayList<>();
        tmp.add(value*2);tmp.add(moveCnt + 1);
        queue.add(tmp);
      }

      //1더하기
      if (value*10 + 1 < end) {
        tmp = new ArrayList<>();
        tmp.add(value*10 + 1);tmp.add(moveCnt + 1);
        queue.add(tmp);
      }
    }

    if (result == -1)
      System.out.println(-1);
    else
      System.out.println(result + 1);
  }
}

• 최소 연산 횟수 순으로 queue에 들어가니 이 문제는 bfs로도 풀 수 있다. (물론 그리디가 시간이 훨씬 빠름)
• queue에 시작숫자와 이동수에 대한 리스트를 넣어준다
• queue가 빌 때까지 반복한다
  • queue에서 리스트를 하나 빼서 value, moveCnt에 저장한다
  • 해당 숫자 * 2 가 end보다 작다면 queue에 넣어주고
  • 해당 숫자 * 10 + 1이 end보다 작다면 queue에 넣어준다
  • 만약 해당 숫자 * 2 나 해당 숫자 * 10 + 1 한 값이 end와 같아지면 해당 moveCnt를 result에 넣어주고 반복문을 종료한다
• result에 1을 더한 값을 출력한다

 

 

Long 타입으로 안받았더니 엄청 틀렸다 ㅜㅜ 최대 저장될 수 있는 숫자를 잘 확인해야겠다