[JAVA] 알고리즘 스터디 3주차 공통과제: 숨바꼭질 | 백준 #1697 | Dynamic Programming

백준 #1697 숨바꼭질 

🔒 문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

⌨️ 입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

🖥️ 출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

 

---

🔎  풀이

나는 DP를 이용해서 문제를 풀었다. times[] 배열은 술래의 위치 START로부터 각 index까지 도달하는데 걸리는 최소 시간을 담는다. 

우선 초기화할 때 0부터 START까지는 START - i 값을 담는다. START에서 START보다 작은 i까지 가는데 걸리는 시간은 한 걸음씩 (START-i)번 걸어가는데 걸리는 시간과 같기 때문이다.

그 다음에는 dp를 실행한다. dp는 크게 n이 홀수거나 짝수거나 두 가지 경우로 나뉜다. 그렇게 나누는 이유는 n이 짝수면 순간이동이 가능하고, 홀수면 순간이동을 할 수 없기 때문이다. 

 

먼저 n이 홀수인 경우를 살펴보자. n이 홀수라면 순간이동은 불가하고 인접한 좌표인 n-1이나 n+1에서 걸어오는 방법 밖에 없다. 그러므로 두 가지 경우를 계산해 둘 중 더 작은 값을 times[n]에 담아주면 된다. 

 

n-1에서 걸어오는 것은 쉽게 times[n-1] + 1로 구할 수 있지만 n+1에서 걸어오는 경우는 times[n+1]+1이렇게 구할 수 없다. for문은 START + 1부터 1씩 늘어나면서 실행되고 있으므로 times[n+1]에 담긴 값은 초기화가 되지 않은 값(0)이기 때문이다. 그런데 n+1은 짝수인 점을 활용하면 times[n+1]은 times[(n+1)/2]에서 순간이동한 값과 같음을 알 수 있다. 그러므로 n이 홀수일 때 점화식은 다음과 같다.

if(n%2!=0) times[n] = Math.min( times[n-1] + 1, times[(n+1)/2]+2 );

 

---

 

n이 짝수인 경우는 다음과 같이 세 가지 경우가 있다. 홀수와 동일하게 인접한 두 좌표에서 걸어오는 경우와 '순간이동'하는 경우까지 포함된다. 이 세 경우 중 최솟값에 1을 더하면 times[n]을 구할 수 있다.

먼저 순간 이동하는 경우에는 times[n/2] + 1, n-1에서 걸어오는 경우는 times[n-1]+1이다.

그런데 여기서 n+1에서 걸어오는 경우는 어떻게 구할까?

우선 n+1은 초기화가 일어나지 않은 홀수 좌표이므로 위에서 홀수 좌표의 경우를 따져봤던 것 처럼 인접한 좌표에서 걸어오는 경우를 구해본다. 그런데 이때 n+1을 기준으로 인접한 이전 좌표에서 걸어오는 경우는 times[n]이다. 이는 현재 우리가 구하려는 경우니까 패스. 

그럼 n+1을 기준으로 인접한 다음 좌표에서 걸어오는 경우는 times[n+2]이다. 해당 좌표 또한 현재 초기화가 되어있지 않은 '짝수'좌표니까 순간이동하기 전 좌표를 사용해서 구하면 times[(n+2)/2]+1가 times[n+2]이다.

그럼 times[n]은 times[n+2]보다 2칸 전에 있으니까 결국 times[(n+2)/2]+3이다.

(그런데 다른 사람들의 DP 풀이를 찾아보니까 모두 n이 짝수일 때는 n+1에서 걸어오는 경우를 고려하지 않았다. 그 점이 이해가 가지 않아서 나는 이 경우고 고려하는 방향으로 풀었다. )

 

총 세 가지 경우를 사용해 점화식으로 표현하면 다음과 같다. 

if(n%2==0) times[n] = Math.min(Math.min(times[n/2] + 1, times[n-1] + 1 ), times[(n+2)/2]+3 );

 

🔹 전체 코드

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

public class Main {
    static int START;
    static int END;
    static int[] times = new int[100001];

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer line = new StringTokenizer(bf.readLine(), " ");

        START = Integer.parseInt(line.nextToken());
        END = Integer.parseInt(line.nextToken());

        if( START >= END ){
            System.out.println( START - END );
            return;
        }

        for( int i = 0; i <= START; i++ ){
            times[i] = START - i;
        }

        dp();

        System.out.println(times[END]);

    }// end of main

    static void dp( ){
        for( int i = START + 1; i < END + 1; i++ ){
            if( i % 2 == 0 ){
                times[i] = Math.min(Math.min(times[i/2] + 1, times[i-1] + 1 ), times[(i+2)/2]+3 );
            }
            else{
                times[i] = Math.min( times[i-1] + 1, times[(i+1)/2]+2 );
            }
        }
    }// end of dp
    
}// end of class

 

- 시간 복잡도: O(N)

- 공간 복잡도: O(N)