boj 1229 육각수

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

 

간단한 dp 문제입니다.

문제가 요구하는 육각수들의 수를 미리 구한 다음 N을 만들기 위해 필요한 육각수의 갯수를 구하여 해결할 수 있습니다.

 

육각수의 수는

1 * 1

2 * 3

3 * 5

4 * 7

5 * 9

이렇게 규칙을 찾을 수 있고, An = n * (2n - 1) 으로 구할 수 있습니다.

 

dp[i] = i를 만들기 위해 필요한 육각수의 최소 갯수

인덱스가 갯수이므로 dp[i] = dp[i - 현재 육각수의 갯수] + 1으로 최솟값을 갱신할 수 있습니다.

 

 

#include <iostream>
#define MAX_N 1000001
#define MAX_M 710
using namespace std;
 
int list[MAX_M];
int dp[MAX_N];
int N;
 
void init() {
    for (int i = 1; i < MAX_M; i++) {
        list[i] = i * ((i << 1) - 1);
    }
}
 
void func() {
    init();
 
    dp[1] = 1;
    for (int i = 2; i <= N; i++) {
        dp[i] = 1e9;
        for (int j = 1; j < MAX_M; j++) {
            if (i < list[j]) break;
            dp[i] = min(dp[i], dp[i - list[j]] + 1);
        }
    }
 
    cout << dp[N] << '\n';
}
 
void input() {
    cin >> N;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}