[백준온라인] 1697번 숨바꼭질

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

1697번: 숨바꼭질

문제 요약 : 주어진 점에서 순간이동(+1,-1,*2)을 해서 목표지점까지 가는 최소 횟수

입력	출력
0 ≤ N(시작) ≤ 100000 0 ≤ K(목표) ≤ 100000	목표지점 까지의 최소시간 출력

 

JAVA

채점 번호	아이디	문제 번호	결과	메모리	시간	언어	코드 길이
16533297	cbkpar	1697	맞았습니다!!	15552KB	2200ms	Java	1015B

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

public class Main {
	
	public static void main(String args[]) throws IOException {
		int i,n,k;
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int[] arr = new int[100001];
		int[] tarr = new int[100001];
		n=Integer.parseInt(st.nextToken());
		k=Integer.parseInt(st.nextToken());
		if(n>=k) {
			System.out.println(n-k);
			return;
		}
		for(i=0;i<=100000;i++) {
			arr[i]=999999;
			tarr[i]=999999;
		}
		arr[n]=0;
		tarr[n]=0;
		while(arr[k]==999999) {
        //도달 할때까지 계속해서 새롭게 구한다
			for(i=0;i<100000;i++) if(arr[i]!=999999) tarr[i+1]=Math.min(tarr[i+1], arr[i]+1);
			for(i=100000;i>0;i--) if(arr[i]!=999999) tarr[i-1]=Math.min(tarr[i-1], arr[i]+1);
			for(i=0;i<=50000;i++) if(arr[i]!=999999) tarr[i*2]=Math.min(tarr[i*2], arr[i]+1);
			System.arraycopy(tarr, 0, arr, 0, 100001);
		}
		System.out.println(arr[k]);
	}
}

이 문제를 모든 경우의 수를 생각하여 통과는 하였지만 더욱 효율적인 방법을 떠올리지 못해 2.2초라는 상당한 시간을 소요한 것을 알 수 있다. 더욱 효율적인 방법을 공부해 다음에 다시 풀어봐야 할 것 같다.