백준 12851번
https://www.acmicpc.net/problem/12851
문제
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
출력
첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
둘째 줄에는 가장 빠른 시간으로 수빈이가 동생을 찾는 방법의 수를 출력한다.
예제 입력 1
5 17예제 출력 1
4
2생각하기
혹시나 숨바꼭질2 먼저 푸시는 분들은 1부터 풀어보시길 권장드립니다.
숨바꼭질1의 설명링크입니다.
숨바꼭질1
동작
이번에는 이전 문제인 숨바꼭질1에서 방법의 수도 출력하는 부분이 추가되었다.
방법의 수를 추가하는 것은 숨바꼭질 1을 풀어보신분이라면, 간단하다
그냥 수빈이와 동생이 만날때마다 count를 증가시키면된다.
내가 힘들었던 부분은 count값을 최솟값에 따라 갱신시켜주어야 하나 했는데,
애초에 que에서 계산되는 첫번째가 최단시간이기 때문에 그냥 증가시켜 주면 됬었다.
이전 숨바꼭질1에서는 if(next_time == K) { 조건에서 곧바로 return으로
종료시켰지만, 여기서는 count 증가도 있으니 지속해서 반복해야 한다.
그리고 최소시간보다 que에서 나온 위치의 시간이 더 클 경우
곧 바로 return; 으로 종료해주면 된다.
min_time = Integer.MAX_VALUE/16; 으로 초기화한 것은
그냥 Integer.MAX_VALUE로 설정하면 +를 해주었을 때, Integer범위를 넘어서
Integer.MIN_VALUE 값으로 넘어가버리기 때문에, 그냥 /16을 넣어서 설정해줬다.
(딱히 의미는 없고 그냥 최댓값으로 초기화 한거임)
그리고 한가지 예외케이스를 잊지 말자.
수빈이가 동생보다 더 앞에 있을 때,
수빈이는 순간이동을 앞으로 밖에 못한다. 그럼 뒤로가는 것은 -1 밖에 못한다는 얘기니까.
그리고 방법은 오직 1가지 밖에 없다.
if(N >= K) {
System.out.println(N-K);
System.out.println(1);
return;
}
TMI
숨바꼭질 시리즈는 조금 더 성장하고 3으로 넘어가자..
겨우 한 단계 넘어왔는데, 생각하기가 더 까다로웠다..
코드
BFS
import java.util.*; import java.io.*; public class Main { static Queue<Integer> que = new LinkedList<>(); static int arr[] = new int[100001]; static int N, K; static int min_time, count; static int next_time; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); // 수빈이의 위치 K = Integer.parseInt(st.nextToken()); // 동생의 위치 if(N >= K) { System.out.println(N-K); System.out.println(1); return; } BFS(); System.out.println(min_time); System.out.println(count); } // End of main public static void BFS() { min_time = Integer.MAX_VALUE/16; // 최단 시간 count = 0; que.offer(N); arr[N] = 1; while( !que.isEmpty() ) { int time = que.poll(); if(min_time < arr[time]) { return; } for(int i=0; i<3; i++) { switch(i) { case 0: next_time = time + 1; break; case 1: next_time = time - 1; break; default : next_time = time * 2; } if(next_time == K) { min_time = arr[time]; count ++; } if( Range_check() && (arr[next_time] == 0 || arr[next_time] == arr[time] + 1) ) { que.offer(next_time); arr[next_time] = arr[time] + 1; } } } } // End of BFS // 범위 체크 static boolean Range_check() { return (next_time >= 0 && next_time <= 100000); } // End of Range_check } // End of class
