[백준] 1229번 육각수 C++

문제 출처: https://www.acmicpc.net/problem/1229

1229번: 육각수

육각수의 크기를 미리 구해놓고

dp[현재 값]에서 dp[현재 값 - 육각수의 크기] + 1로 비교해가며 min값을 갱신 해주며 풀었다.

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include <string>

using namespace std;
int arr[1001];
int dp[1000001];
const int INF=123456789;

int main() {
    ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    
    int N;
    cin >> N;
  
    arr[1] = 1;
    int idx;


    fill(&dp[0], &dp[1000001], -1);

    for (int i = 2; i <= 1000; i++) {
        arr[i] = arr[i - 1] + 4 * i - 3;
        if (arr[i] >= 1000000)break;
        dp[arr[i]] = 1;
    }


    dp[1] = 1;
    for (int i = 2; i <= N; i++) {
        int val = INF;
        
        for (int j = 1; j <= 1000; j++) {
            if (val == 1 || val == 2)break;
            if (i < arr[j])break;
            if (i == arr[j])val = min(val,1);
            else {
                val = min(val,dp[i - arr[j]] + 1);
            }
        }
        dp[i] = val;
    }

    cout << dp[N];

    
}