[Algorithm] Baekjoon 1660번 : 캡틴 이다솜

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

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
int n;
int triangles[1001] = { 0 };
int tetraherons[1001] = { 0 };
int dp[300001] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    memset(dp, 0x3f, sizeof(dp));
    int maxTetrahedronSizeIndex = 0;
    for (int i = 1; i <= 1000; ++i)
    {
        triangles[i] = triangles[i - 1] + i;
        tetraherons[i] = tetraherons[i - 1] + triangles[i];
 
        if (tetraherons[i] > n)
        {
            maxTetrahedronSizeIndex = i-1;
            break;
        }
    }
 
    dp[0] = 0;
    for (int i = 1; i <= maxTetrahedronSizeIndex; ++i)
    {
        int tetrahedron = tetraherons[i];
 
        for (int j = tetrahedron; j <= n; ++j)
        {
            dp[j] = min(dp[j], dp[j - tetrahedron] + 1);
        }
    }
 
    cout << dp[n];
}
 
 
 

 

이 문제같은경우는 사실 동전시리즈 문제중 하나로 치환할 수 있다.

사면체를 만드는 방법이 주어지고, 여러크기의 사면체가 존재하게되는데 해당 사면체들을 사용해서 딱 n개만큼의 대포알만 소모하게하는 문제이다.

각 크기의 사면체마다 소모되는 대포알개수를 알고있다 가정하면, 이 대포알개수는 동전단위로 볼수 있다.

문제에서 사면체각각의 크기에대한 개수제한이 없기 때문에, 무한히 쓸 수 있다 가정하면 이 문제는 결국

각각의 무한히 쓸 수 있는 동전이 주어졌을 때, n값의 금액을 맞추는 최소의경우의 수를 구하는 문제이다.