[백준] 1463 1로 만들기 - Dynamic Programming / Java

• 문제 링크

1463번: 1로 만들기

 

• 풀이 과정

1 ~ n 까지의 각각의 수를 문제에 제시된 조건에 맞는 연산을 하여

최소 연산이 되는 횟수를 저장할 dp 배열을 n + 1 의 크기로 생성한다.

 

i가 1 ~ 10 의 범위일 경우 i - 1, if (i % 2 == 0) i / 2, if (i % 3 == 0) i / 3 의 연산 중

최소 횟수의 연산을 각각의 dp 배열 인덱스에 저장하면 아래와 같다.

0	1	2	3	4	5	6	7	8	9	10	11
0	0	1	1	2	3	2	3	3	2	3	-

예를 들어 n = 6 일 경우 문제에 제시된 3가지 연산이 모두 가능하며,

i - 1 = 6 - 1 = 5, dp[5] 에 저장된 연산 횟수에 1을 더하면 dp[6] = dp[5] + 1 = 4,

i / 2 = 6 / 2 = 3, dp[3] 에 저장된 연산 횟수에 1을 더하면 dp[6] = dp[3] + 1 = 2,

i / 3 = 6 / 3 = 2, dp[2] 에 저장된 연산 횟수에 1을 더하면 dp[6] = dp[2] + 1 = 2,

즉 위의 연산 횟수 중 최솟값은 2이므로 dp[6] = 2 로 저장된다.

 

이로 미루어 보았을 때 이전의 연산 횟수의 값이 저장되어 있어야 이후의 연산 횟수를 구할 수 있음을 알 수 있고,

이런식으로 각각의 1 ~ n 의 수가 1이 되기 위한 연산 횟수를 순차적으로 메모이제이션하여

dp[n] 에 저장된 연산의 횟수를 정답으로써 출력한다.

 

추가적으로 dp[0] = dp[1] = 0 으로 초기화하는 것이 원칙이나 이 문제의 경우 생략 가능하다.

 

• 풀이 코드

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

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));

		int n = Integer.parseInt(br.readLine());
		int[] dp = new int[n + 1];

		for (int i = 2; i < n + 1; i++) {
			dp[i] = dp[i - 1] + 1;

			if (i % 2 == 0)
				dp[i] = Math.min(dp[i], dp[i / 2] + 1);
			
			if (i % 3 == 0)
				dp[i] = Math.min(dp[i], dp[i / 3] + 1);
		}

		bw.write(dp[n] + "\n");
		bw.flush();
	}

}