1697

숨바꼭질

 

 

KeyPoint : 

1. 레벨 탐색

2. 방문했던 x 위치가 나오면 더 진행하지 않는다.

 

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

public class Main {

	static int answer = Integer.MAX_VALUE;
	static int N, K;
	static boolean[] visited;
	static boolean DBG = false;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		visited = new boolean[100001];
		bfs(N);
		System.out.println(answer);
	}

	private static void bfs(int start) {

		Queue<Integer> Q = new LinkedList<>();
		int level = 0;
		Q.offer(start);

		while (!Q.isEmpty()) {

			int len = Q.size();
			for (int i = 0; i < len; ++i) {
				int x = Q.poll();
				
				if( x < 0 || x > 100000 )
					continue;
				
				if (x == K) {
					Q.clear();
					answer = level;
					break;
				}
				if (!visited[x]) {
					visited[x]=true;
					Q.offer(x + x);
					Q.offer(x + 1);
					Q.offer(x - 1);
				}
				
			}
			level++;
		}

	}

}

 

 

참고..

DP로 해결한 멋진 방법

 

1. 현재 위치까지 dp를 초기화

ex)   

x = 4

dp[0]=4

dp[1]=3

dp[2]=2

dp[3]=1

dp[4]=0

 

2. dp를 점진적으로 채워간다,

+1의 방법과 *2의 방법 중 더 작은 값을 선택.

dp[i] 위치가 2의 배수인 경우, dp[i/2] + 1

dp[i] 위치가 홀수인 경우, dp[i+1/2] + 2 (연산을 두번 필요로함)

 

dp[5] = dp[4] + 1

4%2==0 이므로

dp[5] = min(dp[5] , dp[(5+1)/2] + 2) (  dp[3]에서 x*2 방법으로 6으로 온 뒤, 뒤로 한칸 -> dp[3] + 2) 

 

위의 방식으로 dp[k]를 계산한다.

 

//https://www.acmicpc.net/source/11454487

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		int[] dp = new int[n+k+2];
		for (int i=n-1,j=1; i>=0 ; i--,j++) {
			dp[i]=j;
		}
		for (int i = n+1; i < k+1; i++) {
			dp[i] = dp[i-1]+1;
			if(i%2==0) dp[i] = Math.min(dp[i], dp[i/2]+1);
			else dp[i] = Math.min(dp[i], dp[(i+1)/2]+2);
		}
		System.out.println(dp[k]);
	}

}