문제 1229

풀이접근

1. 해당 문제는 dp로 접근해 보자!
2. N이 1~5일 경우는 1개 짜리가 N개씩 있다.
3. N이 6~ 11일 경우에는 6개 짜리 하나와 N-6개의 1개짜리가 있다.
4. 2번과 3번을 d라는 배열에 미리 담아둔다.
5. 만약 13보다 낮은 N값이면 d 배열에 있는 값을 출력하고, 13 이상이면 dp배열에 d배열의 값을 넣어준다.
6. get이라는 매소드를 만들어서 N보다 작거나 같은 육각수의 값들을 저장하여 ArrayList로 받아온다.
7. 13~N까지 차례대로 list의 값을 가지고 dp[i]의 최소값을 저장하자.
   1.예시) i=13 일 때, Math.min(dp[13-1], dp[13-6]) + 1
   dp[13-15]부터는 a가 크니까 break
8. 나온 결과 값을 출력한다.

소스코드

import java.io.*;
import java.util.*;
public class boj1229 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] d = {0, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 6, 2};
        int[] dp = new int[N + 1];
        if (N < 13) {
            System.out.println(d[N]);
        } else {
            for (int i = 0; i < d.length; i++) {
                dp[i] = d[i];
            }
            // 육각수들을 뽑아냄
            ArrayList<Integer> list = get(N);
            for (int i = 13; i < N + 1; i++) {
                int min = Integer.MAX_VALUE;
                for (int a : list) {
                    if (a > i) {
                        break;
                    }
                    min = Math.min(min, dp[i - a]);
                }
                dp[i] = min + 1;
            }
            System.out.println(dp[N]);
        }
    }
    public static ArrayList<Integer> get(int limit) {
        int n = 1;
        int current = 0;
        ArrayList<Integer> list = new ArrayList<>();
        while (current <= limit) {
            current = n * (2 * n - 1);
            list.add(current);
            n += 1;
        }
        return list;
    }
}

문제 핵심

• DP