[백준/boj] 1463: 1로 만들기 (Java) / DP

문제

1463번: 1로 만들기

풀이

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

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static int N;
	static int[] dp = new int[1000001];

	public static void main(String[] args) throws Exception {
		N = Integer.parseInt(br.readLine());
		dp[0] = 0;
		dp[1] = 0;
		dp[2] = 1;
		dp[3] = 1;
		int value;
		for (int i = 4; i <= N; i++) {
			value = i - 1;
			dp[i] = dp[value] + 1;
			if (i % 3 == 0) {
				value = i / 3;
				dp[i] = Math.min(dp[value] + 1, dp[i]);
			}
			if (i % 2 == 0) {
				value = i / 2;
				dp[i] = Math.min(dp[value] + 1, dp[i]);
			}
		}
		System.out.println(dp[N]);
	}
}

dp[n]은 n이 1이 되는 연산 최솟 값을 담는다.

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

연산 조건이 위와 같으므로, dp[1] = 0; dp[2] = 1; dp[3] =1; 은 미리 설정해줄 수 있다. 다음 dp[4] 부터 채워나간다.

• dp[n-1]은 항상 존재하기 때문에 맨 처음엔 dp[n-1] + 1 (n - 1 이라는 연산을 한번 했으니까 연산 횟수 1을 더해줘야함)을 dp[n]에 할당한다. 예를 들어 n이 4이면 4 에서 1을 뺀 값인 3의 연산 최솟값에 연산 한번을 더한 값을 할당해 주는 것이다.

근데 이게 최소라는 보장은 없다. 그러므로 3 또는 2로 나눠지는지 본다.

• n을 3으로 나눈 나머지 값이 0일때, dp[n /3] (=> n을 3으로 나눈값이 1이 되기위해 연산한 횟수의 최솟값이 담겨있음) +1 (=> n을 3으로 나누는 연산을 했기 때문에 1을 더해야함.)이 for문에서 처음 할당한 dp[n]값보다 작다면 dp[n] = dp[n/3]+1로 바꿔준다.
• n을 2로 나눈 나머지 값이 0일때, 3과 동일하게  dp[n /2] +1이 지금까지 할당되어 있는 dp[n]값보다 작다면 dp[n] = dp[n/2]+1로 바꿔준다.

위 과정이 끝나면 dp[n]에는 사용할 수 있는 연산을 사용해 1을 만든 연산의 수 중 가장 최솟값이 담기게 된다. 이 뒤로 n 보다 큰 아이들은 dp[n]이 최솟값임을 알기 때문에 이를 이용해서 자신의 최솟값을 채우게 될것이다!