[DP]숨바꼭질(백준 1697번), 자바(★☆)

1697번: 숨바꼭질 (acmicpc.net)

1697번: 숨바꼭질

 

고려해야 될 부분

1. N이 0인 경우

2. K가 N보다 왼쪽에 있는 경우 

 

 

if(i%2)==0 이면 dp[i]=Math.min(dp[i/2]+1, dp[i-1]+1)

if(i%2)!=0 이면 dp[i]=Math.min(dp[i-1]+1, dp[i+1]+1)

import java.util.*;

public class Main {
	

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