육각수

https://www.acmicpc.net/problem/1229

소스코드

Main

 public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();

        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]);
                //육각수만큼의 값을 뺐을 때 최솟값
                // 13일때 2 , 26 일때 5 130 일때 4 네
            }
            dp[i] = min +1;
        }
        System.out.println(dp[N]);
    }
    //즉 d[] 배열에 있는 최소갯수가 계속 도는데
    // dp[i-a]로 해서 13개 값중에 최솟값을 찾고
    // +1 해주면 그게 정답.

생각할 것

1. 0 ~ 12 까지 최소갯수가 도는 배열
2. N보다 작은 육각수를 만들고 어떻게 꺼내서 써볼것인지

참고

https://latte-is-horse.tistory.com/322

https://velog.io/@phc09188/%EB%B0%B1%EC%A4%80-%EC%9C%A1%EA%B0%81%EC%88%981229