백준 1697번
https://www.acmicpc.net/problem/1697

문제

---

생각하기

---

• BFS를 통해서 푸는 문제이지만, 정해진 규칙이 있기 때문에 DP로도 풀 수 있는 문제였다.

생각해보면 어떤 위치에서 출발하건 해당하는 위치에서의 최솟값은 변하지 않음을 생각해야 한다. 짝수위치 에서는 당연히 순간이동해서 온 시간이 최단시간이 될 것이고, 홀수 위치에서는 한칸 앞의 위치에서 이전에 순간이동을 해온 시간, 또는 한칸 뒤의 위치에서 순간이동을 해온 시간 중 2개중에 하나가 최단시간이 된다.

가령, 각각 다른 10개의 테스트 케이스를 돌려서 distance[10]의 위치를 계속 파악한다고 했을 때, distance[10]의 최솟값은 항상 똑같다

동작

코드

---

Java

import java.io.*;
import java.util.*;

public class Main {
	static int distance[] = new int[100001]; // 전체 거리
	static int N, K;	
	
	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);
			return;
		}
		
		for(int i=0; i<N; i++) {
			distance[i] = N-i;
		}
		
		DP();
		System.out.print(distance[K]);
	} // End of main
	
	private static void DP() {
		for(int i=N+1; i<=K; i++) {
			int min;
			
			if(i % 2 == 0) {
				min = distance[i/2] + 1;
			}
			else {				
				min = Math.min(distance[(i+1)/2], distance[(i-1)/2]) +2;
			}
			
			distance[i] = Math.min(min,  distance[i-1]+1);
		}
	}// End of DP
} // End of class

Kotlin