[BOJ] 1229 - 육각수 (Java)

1229번: 육각수

접근법

점화식을 잘 세우면 금방 풀 수 있는 문제

이 식을 잘 도출할 수 있다면 다음 필요한 dp를 구하는 것은 어렵지 않다.

육각수 배열을 h라 할 때, dp[n]은 h[i]값이 n을 넘지 않는 한에서, dp[n-h[i]]의 최솟값을 구하면 된다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

	static final int MAX_N = 146858;
	static int[] six_angle = new int[MAX_N + 1];
	static int[] dp;

	public static void main(String[] args) throws IOException {
		int N = Integer.parseInt(br.readLine());
		process_six_angle();

		dp = new int[N + 1];
		Arrays.fill(dp, MAX_N);
		dp[0] = 0;
		dp[1] = 1;

		for (int i = 2; i <= N; i++) {
			for (int j = 1; j <= i; j++) {
				if (six_angle[j] > i) {
					break;
				}
				if (dp[i - six_angle[j]] + 1 < dp[i]) {
					dp[i] = dp[i - six_angle[j]] + 1;
				}
			}
		}
		System.out.println(dp[N]);

	}

	public static void process_six_angle() {
		six_angle[1] = 1;
		for (int i = 2; i <= MAX_N; i++) {
			six_angle[i] = (i - 1) * 6 + six_angle[i - 1] - (2 * (i - 1) - 1); // hn에 대한 점화식
		}
	}
}

결과

메모리	시간	언어
18700KB	1268ms	Java