[백준] 1697 숨바꼭질 [java]

문제

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

풀이

수평선에 시작점에서 끝점까지 이동하는 최소 거리를 구하는 것으로 전형적인 dp 문제이다.
생각해보면, 시작점에서 왼쪽으로 가는 방법은 한 칸씩 이동하는 방법밖에 없으므로, dp배열에서 시작점부터 0까지는 1씩 더해저 저장해주면 된다. 시작점에서 오른쪽으로 가는 방법은 한 칸씩 이동하거나 2배 점프하는 방법이 있는데, 이때, 잘 생각해야 할 점은, 뒤로 돌아올 수 있다는 점이다. 따라서, 현 지점에서 뒤로 한칸 가는 경우까지 계산해줘야 한다.
예를 들어, 이 문제의 예제에서

9로 가는 방법은 5 -> 4 -> 8 -> 9 로 3이다. 그런데,

10으로 가는 경우를 구하고 나면, 5 -> 10 -> 9 로 2가 된다.
따라서 배열을 선언할 때, 끝나는 지점 + 1을 해주어 뒤로 가는 경우도 고려하도록 해야 한다.

코드

import java.util.Scanner;

// dp. 현 위치에서 양 옆으로 이동하면서 탐색하면서 +1 더하는 경우 or 2로 나누는 경우를 비교해서 작은거 dp배열에 넣음. 근데 이때, 홀수이면 2로 못나눔
// 각 지점에서 뒤와 앞으로 가는 모든 경우를 저장하기
public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int start = scanner.nextInt();
        int end = scanner.nextInt();
        int[] dp = new int[Math.max(start, end) + 2];

        int ans = 0;
        if(end < start){
            ans = start - end;
        }
        else{
            int curr = start - 1;
            while(curr >= 0){                   //시작 위치의 왼쪽은 그냥 한칸씩 움직이는 방법밖에 없음.
                dp[curr] = dp[curr + 1] + 1;
                curr--;
            }
            curr = start + 1;
            while(curr <= end + 1){
                if(curr % 2 != 0){      //홀수이면
                    dp[curr] = dp[curr - 1] + 1;
                }
                else{
                    dp[curr] = Math.min(dp[curr - 1] + 1, dp[curr / 2] + 1);
                    dp[curr - 1] = Math.min(dp[curr] + 1, dp[curr - 1]);        //현재 탐색중인 것의 왼쪽도 확인
                }
                curr++;
            }
            ans = dp[end];
        }

        System.out.println(ans);
    }

}