algorithms
코드포스 (codeforces)
코드포스 520B (codeforces 520B)
·
코드포스 520B (codeforces 520B) 문제 풀이 및 코드 (description and code)
Problem - 520B - Codeforces
코드
import java.io.*;
import java.util.Arrays;
public class CF520B {
static int n, m, ans = 0;
static String ins[];
static int[] dp = new int[20001];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
ins = br.readLine().split(" ");
n = Integer.parseInt(ins[0]);
m = Integer.parseInt(ins[1]);
if (m < n) ans = n - m;
else {
Arrays.fill(dp, 100000);
dp[n] = 0;
for (int i = n; i > 1; i--) {
dp[i - 1] = dp[i] + 1;
}
for (int i = 1; i <= (m << 1); i++) {
if (i % 2 == 0) dp[i] = Math.min(dp[i], dp[i / 2] + 1);
}
ans = dp(m);
}
bw.write(ans + "\n");
bw.flush();bw.close();
}
public static int dp(int k) {
if (k > (m << 1)) return 100000;
if (dp[k] != 100000) return dp[k];
else {
if (k % 2 == 0) dp[k] = dp(k >> 1) + 1;
dp[k] = Math.min(dp[k], dp(k + 1) + 1);
return dp[k];
}
}
}