[백준] 25418 정수 a를 k로 만들기 - Dynamic Programming / Java

• 문제 링크

25418번: 정수 a를 k로 만들기

 

• 풀이 과정

dp[i] 를 a 를 i 로 만들기 위한 최소 횟수로 정의한다.

 

i가 짝수이고, i 를 2 로 나눈 값이 n 이상일 경우 2배 연산이 가능하므로,

dp[i] 는 이전 더하기 1 연산과 2배 연산 횟수 중 작은 값에 1를 더한 값이 된다.

그 외는 이전 더하기 연산 횟수의 1을 더한 값으로 지정한다.

 

• 풀이 코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int[] dp = new int[k + 1];

        for (int i = n + 1; i <= k; i++)
            dp[i] = (i / 2 >= n && i % 2 == 0 ? Math.min(dp[i - 1], dp[i / 2]) : dp[i - 1]) + 1;

        bw.write(String.valueOf(dp[k]));
        bw.flush();
    }

}