[다이내믹 프로그래밍] 백준 1697번 숨바꼭질 [Java]

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

public class Main {
	static int[] graph;
	
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        
        graph = new int[Math.max(N, K) * 2 + 1];
        graph[N] = 0;

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

    }
    
}

 

https://www.acmicpc.net/submit/1697/92858044

다이내믹 프로그래밍으로 풀었다

 

K가 N보다 적을 때에는 뒤로 -1씩 하는 수밖에 없기 때문에 N에서 i만큼 뒤로 가는 수를 더하고

N과 같을 때에는 0

N보다 큰 경우에만 분기로 나누어 처리했다.