[Java] 백준 13549번 :

쉬운 목차

1. 문제

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

#13549: 숨기기 3

수빈은 남동생과 숨바꼭질을 하고 있다.

수빈은 현재 포인트 N(0 ≤ N ≤ 100,000)에 있고 그녀의 오빠는 포인트 K(0 ≤ K ≤ 100,000)에 있습니다.

수빈은 걷거나 텔레포트할 수 있다.

수빈의 위치가 X일일 때

www.acmicpc.net

2. 솔루션 프로세스

(방법 1) PriorityQueue가 있는 BFS

도착점이 출발점보다 작으면 그냥 빼는 것이 가장 빠르기 때문에 NK가 반환된다.

그렇지 않은 경우 PriorityQueue를 사용하고 현재 최소 경로인 값에 대해 +1, -1, *2를 시도합니다.

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

public class Main {

    public static void main(String() args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String() inputs = br.readLine().split(" ");
        int N = Integer.parseInt(inputs(0));
        int K = Integer.parseInt(inputs(1));
        
        if(K <= N){
            System.out.println(N-K);
        }
        else{
            boolean() visited = new boolean(100_001);
            PriorityQueue<int()> pq = new PriorityQueue<>((o1, o2)->o1(1)-o2(1));
            pq.add(new int(){N, 0});

             while(!
pq.isEmpty()){
                int() now = pq.poll();
                if(now(0) == K){
                    System.out.println(now(1));
                    break;
                }
             
                visited(now(0)) = true;

                if(now(0) - 1 >= 0 && !
visited(now(0) - 1)){
                    pq.add(new int(){now(0) - 1, now(1) + 1});
                }
                if(now(0) + 1 <= 100000 && !
visited(now(0) + 1)){
                    pq.add(new int(){now(0) + 1, now(1) + 1});
                }
                if(now(0) * 2 <= 100000 && !
visited(now(0)*2)){
                    pq.add(new int(){now(0)*2, now(1)});
                }
            }
        }
        
    }
}

결과

(방법 2) DP

짝수라면 앞에 있는 +1 케이스와 앞에 있는 *2 케이스만 고려하면 됩니다.

바로 뒤에 오는 값이 홀수이기 때문입니다.

짝수가 아닌 경우 +1이 앞에 있고 -1이 뒤에 있는 두 경우 중 최소값을 찾아야 합니다.

i+1번째 숫자는 dp(i)+1 또는 dp((i+1)/2)의 최소값을 고려하므로 항상 i번째에서 전자보다 작으므로 후자만 고려됩니다.

따라서 식은 Math.min(dp(i-1) + 1, dp((i+1)/2) + 1)이 됩니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

    public static void main(String() args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String() inputs = br.readLine().split(" ");
        int N = Integer.parseInt(inputs(0));
        int K = Integer.parseInt(inputs(1));
        int() dp = new int(K+1);

        if(K <= N){
            System.out.println(N-K);
        }
        else{
            for(int i=0; i<N; i++){
                dp(i) = N-i;
            }
            for(int i=N+1; i<=K; i++){
                if(i%2==0){
                    dp(i) = Math.min(dp(i/2), dp(i-1) + 1);
                }
                else{
                    dp(i) = Math.min(dp(i-1) + 1, dp((i+1)/2) + 1);
                }

            }
            System.out.println(dp(K));
        }

    }
}

결과