[BOJ] 1660 - 캡틴 이다솜

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

BOJ - 캡틴 이다솜

문제 유형: 다이나믹 프로그래밍

문제 난이도: Gold V

시간 제한: 2초

메모리 제한: 128MB

 

문제

캡틴 이다솜은 자신의 해적선에 적을 공격하기 위한 대포알을 많이 보관해 놓는다. 다솜이는 미적감각이 뛰어나기 때문에, 대포알은 반드시 사면체 모양으로 쌓아놓아야 한다고 생각한다. 사면체를 만드는 방법은 길이가 N인 정삼각형 모양을 만든다. 그 위에 길이가 N-1인 정삼각형 모양을 얹고 그위에 계속 해서 얹어서 1크기의 정삼각형 모양을 얹으면 된다.

예를 들어, 사이즈가 3크기의 한 더미 모양은 다음과 같다.

  X

  X
 X X

  X
 X X
X X X

각각의 삼각형은 1, 3, 6, 10 ,..... 와 같이 대포알을 가지고 있다. 따라서 완벽하게 쌓았을 때, 한 사면체에는 1, 4, 10, 20 ,.... 개를 가지고 있을 것이다.

현재 다솜이의 해적선에 대포알이 N개가 있다. 다솜이는 영식이를 시켜서 사면체를 만들게 하고 싶다. 영식이는 물론 하기 싫지만 어쩔수 없이 다솜이가 시키는대로 사면체를 가능한 최소 개수 만큼 만들려고 한다. N개의 대포알로 만들 수 있는 사면체의 최소 개수를 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에 입력 N이 들어온다. N은 300,000보다 작거나 같은 자연수이다.

 

출력

첫째 줄에 영식이가 만들 수 있는 사면체 개수의 최솟값을 출력한다.

 

풀이

사면체의 종류들은 수열을 이용해서 쉽게 생성할 수 있다.

점점 2, 3, 4, ...씩  누적값이 누적된다.

 

dp[남은 대포알] = 최소 사면체 개수의 꼴로 저장할 것이다.

이를 이용해서 재귀를 호출해서 남은 대포알 수가 0이라면 0을 반환하고, 아니라면 만들 수 있는 대포알들로 각각 만드는걸 시도해서 그 dp값+1들중 최소를 리턴한다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

int solve(int left, vector<int>& a, vector<int>& dp) {
    if (left == 0) return 0;
    if (dp[left] != -1) {
        return dp[left];
    }

    int res = INT_MAX;
    for (int i = 0; i < a.size(); i++) {
        if (left - a[i] >= 0) {
            res = min(res, solve(left - a[i], a, dp) + 1);
        }
    }

    return dp[left] = res;
}

int main(int argc, char* argv[]) {
    int n;
    cin >> n;

    vector<int> a;
    vector<int> dp(n + 1, -1);
    int k = 1;
    int j = 2;
    for (int i = 1; i <= 300000; i += k) {
        a.emplace_back(i);
        k += j;
        j++;
    }

    cout << solve(n, a, dp) << "\n";

    return 0;
}