아이디어

“런타임 전의 전처리”

• 육각수 $h_n$를 수식으로 구할 수 있다. 미리 필요한 $h_n$를 모두 구해놓았다.
  • $n$일 때 육각형은 한 변이 $n$인 육각형이 추가되고(점 개수: $6(n-1)$) 이 중 $2n-3$개의 점이 겹친다.
  • 따라서 $h_n = h_{n-1} + 6(n-1) - (2n - 3) = h_{n-1} + 4n - 3$ (계차수열)
  • $4k - 3$를 $k=1$부터 $n$까지 더하는 식이므로 $h_n = \sum_{k=1}^n(4k-3) = 2n^2-n$

DP

• DP를 통해 순차적으로 육각수 최대개수를 구해서, 마지막으로 n에 해당하는 것을 출력하면 된다.
  • 초기값은 문제에서 주어진 초기 12항으로부터 시작하였다.
  • 사실 그냥 초기값으로 1만 주고 시작해도 된다.
• $n ≤ 12$라면 이미 주어진 최대개수를 그대로 출력하고 끝내면 된다.
• $n > 12$라면 (n - 육각수)들의 육각수 최대개수 중 최소를 취해 1을 더한 값을 n의 육각수 최대개수로 한다.
• 이때 편의상 0의 육각수 최대개수는 0이라 하자.
  • 그렇게 한다면 n이 육각수일 때 (n - 육각수) 중 육각수 최대개수를 최소로 만드는 육각수는 자기 자신 n이라 할 수 있다. (n - n = 0의 육각수 최대개수는 0이고 이보다 더 작은 것은 없으므로)

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;

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

    static int n;
    // 합을 이루는 육각수들의 최소 개수
    static int[] hexMins = new int[1000001];
    // 육각수 h_n
    static int[] h = new int[1000];

    public static void main(String[] args) throws Exception {
        // init: n 최댓값 100만 이하의 모든 육각수 계산
        int i = 1;
        while (true) {
            int eval = i * (2*i - 1);
            if (eval > 1_000_000) break;
            h[i++] = eval;
        }
        int hlen = i - 1;

        // init: 문제에서 주어지는 육각수 최소개수를 미리 적음
        // 편의상 hexMins[0] = 0;
        int[] givenHexMins = new int[] {0, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 6, 2};
        for (i = 0; i < givenHexMins.length; i++) hexMins[i] = givenHexMins[i];

        // start
        n = Integer.parseInt(rd.readLine());

        // 만약 주어져있다면, 그대로 출력하고 끝
        if (n < givenHexMins.length) {
            System.out.println(givenHexMins[n]);
            return;
        }

        // 주어져 있지 않다면 n까지 전부 육각수 최소개수를 구해보자.
        // 자신의 최소개수는 ([자신 - 자신보다 작은 육각수]의 최소개수의 최소 + 1)이 된다.
        // 한편, 편의상 0의 육각수 최소개수는 0이라 하면 자기 자신이 육각수일 때 육각수 최소개수가 1임을 나타낼 수 있다.
        for (i = givenHexMins.length; i <= n; i++) {
            int minHexMin = Integer.MAX_VALUE;
            for (int j=1; j<=hlen; j++) {
                if (h[j] > i) break;
                minHexMin = Math.min(minHexMin, hexMins[i - h[j]]);
            }
            hexMins[i] = minHexMin + 1;
        }

        System.out.println(hexMins[n]);
    }
}

메모리 및 시간

• 메모리: 18132 KB
• 시간: 1224 ms

리뷰

• 아직 DP가 콜롬버스의 달걀이다. 더 연습해보자.
• 미리 문제에서 주어진 값을 쓰지 않는 편이 더 깔끔할 것 같다.
  • 전처리도 필요 없다.

간략화한 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;

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

    static int n;
    static int[] hexMins = new int[1000001];

    public static void main(String[] args) throws Exception {
        n = Integer.parseInt(rd.readLine());

        hexMins[1] = 1;

        // 자신의 최소개수는 ([자신 - 자신보다 작은 육각수]의 최소개수의 최소 + 1)이 된다.
        // 한편, 편의상 0의 육각수 최소개수는 0이라 하면 자기 자신이 육각수일 때 육각수 최소개수가 1임을 나타낼 수 있다.
        for (int i = 1; i <= n; i++) {
            int minHexMin = Integer.MAX_VALUE;
            int j = 1;
            while (true) {
            	int h = j * (2*j - 1);
            	if (h > i) break;
            	minHexMin = Math.min(minHexMin, hexMins[i - h]);
            	j++;
            }
            hexMins[i] = minHexMin + 1;
        }

        System.out.println(hexMins[n]);
    }
}

• 18232 KB / 1120 ms