[백준] S3 25418번 정수 a를 k로 만들기 (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

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

[문제] 

입력으로 양의 정수 A와 K가 주어지면, 아래 연산을 이용하여 A를 K로 변경하려고 한다. 정수 A를 변경할 때 사용할 수 있는 연산 종류는 다음과 같다.

• 연산 1: 정수 A에 1을 더한다.
• 연산 2: 정수 A에 2를 곱한다.

정수 A를 정수 K로 만들기 위해 필요한 최소 연산 횟수를 출력하자.

[입력]

첫 번째 줄에 양의 정수 A와 K가 빈칸을 사이에 두고 순서대로 주어진다.

[출력]

첫 번째 줄에 양의 정수 A를 양의 정수 K로 만들기 위해 필요한 최소 연산 횟수를 출력한다.

 

---

[풀이]

1. 값들을 입력받아준다.

2. dp를 구하기 위한 dp 배열을 만들어준다.

3. n+1 부터 k까지 탐색하며 dp배열을 채워준다.

4. k에 해당하는 최소값을 출력한다.

[접근]

1. 문제를 보자마자 dp를 사용해서 풀면 되겠다고 생각하였다.

2. n부터 k까지 최소횟수를 구하면 되는 문제였다.

3. 점화식

i를 2로 나눈 값이 n이상이고 i를 2로 나눴을 때 나머지가 0인 경우
    dp[i] = Math.min(dp[i - 1], dp[i / 2]) + 1;
아닌 경우
    dp[i] = dp[i - 1] + 1;

[코드]

import java.io.*;
import java.util.*;

public class Main {
	static int n;
	static int k;
	static int[] dp;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		
		// dp 계산을 위한 dp 배열
		dp = new int[k + 1];
		
		// n을 k로 만들어야 하므로 n부터 시작할 것 같지만
		// n일때는 0번이므로 n + 1부터 시작
		for (int i = n + 1; i <= k; i++) {
			// 2배를 할 수 있을 때
			if (i / 2 >= n && i % 2 == 0)
				// 1을 더하는 경우와 2를 곱하는 경우를 비교해서 더 작은 값에 연산횟수 1회 증가
				dp[i] = Math.min(dp[i - 1], dp[i / 2]) + 1;
			else
				// 2배가 불가능 한 경우에는 1더하기 연산만
				dp[i] = dp[i - 1] + 1;
		}
		
		// k의 값을 만드는 최소 횟수가 담긴 배열 값 출력
		System.out.println(dp[k]);
	}
}