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

문제링크 : https://www.acmicpc.net/problem/1229

1229번: 육각수

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

vector<int>v;
int dp[10000001];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    int N;
    cin >> N;

    int num = 1, gap = 5;
    while(num<=N) //가능한 육각수 미리 구해놓기
    {   
        v.push_back(num);
        num+=gap;
        gap+=4; //공차 4
    }
    fill(&dp[0], &dp[10000001], MAX);
    dp[0]=0; dp[1]=1;
    for(auto i : v)
    {
        for(int j=i; j<=N; j++)
        {
            dp[j] = min(dp[j-i]+1, dp[j]); //최소값 갱신
        }
    }

    cout << dp[N];
    return 0;
}

먼저 가능한 육각수에 대해서 구해줬다.

다음과 같이 가능한 육각수들을 보면 규칙을 찾을 수 있다.

ex : 1 6 15 28 45 66
gap : 5, 9, 13, 17, 21 -> 공차가 4인 등차수열

위 규칙을 토대로 초기값인 1부터 gap을 더해주며 N이하로 가능한 최대의 육각수들을 구해서 벡터에 담아줬다.

 

위 벡터에서 담았던 값을 토대로 해당 값부터 N까지의 값을 탐색한다.

이때 dp[j-i]+1 과 dp[j]의 값을 비교하여 작은 값을 저장해준다.

 

처음 육각수인 1을 기준으로 하면 가능한 육각수가 1밖에 없기에 1 ~ 26의 값은 1 ~ 26일 것이다.

그다음 육각수인 6을 기준으로 시작하면 6은 이제 가능한 육각수가 생겼기에 1로 시작하여 11까지는 1 ~ 5일 것이다.

이제 12를 보면 dp[12-6]+1이기에 이는 dp[6]+1로 2인 것을 알 수 있다. 그전값인 dp[6]이 1이기에 해당 값은 2가 된다.

이런식으로 현재 값(12)에 현재 육각수의 값(6)을 빼줌으로써 그전값(6)의 확인을 통해 현재 값이 육각수의 합(6+6)으로 이루어지는지 확인을 할 수 있다.

 

이를 모든 N이하의 가능한 모든 육각수의 경우마다 N까지 탐색을 해서 반복하며, 이때 가장작은 값을 저장해준다.