[ 백준 ] 1660 / 캡틴 이다솜

金弘均·2021년 9월 16일
0

Baekjoon Online Judge

목록 보기
208/228
post-thumbnail
post-custom-banner

# Appreciation

/*
 * Problem :: 1660 / 캡틴 이다솜
 *
 * Kind :: Dynamic Programming
 *
 * Insight
 * - 수열 A : 삼각형에 추가되는 한 줄
 *   수열 B : 길이 N 인 삼각형
 *   수열 C : 길이 N 을 밑면으로 하는 사면체
 *   + N  |  A  B   C
 *     1  |  1  1   1
 *     2  |  2  3   4
 *     3  |  3  6   10
 *     4  |  4  10  20
 *     5  |  5  15  35
 *     6  |  6  21  56
 *     # dp[i] = i 개의 대포알을 사용해서 만들 수 있는 사면체의 최소 개수
 *       라고 정의하고 현재 다루고 있는 사면체를 이루는 대포알의 개수가 k 개일 경우,
 *       dp[i] = min(dp[i], dp[i-k]+1)
 *
 * Point
 * - 아예 수열 C 를 먼저 구한후
 *   Greedy 하게 푸는 방법도 있다 <= N 원이 주어졌을 때 동전을 최소로 사용해서 만들기
 *   + 1, 4, 10, 20, 35, ..., 287980, 295240
 *     ans += N / 295240
 *     N %= 295240
 *     ans += N / 287980
 *     N %= 287980
 *     ...
 *     # 사면체를 이루는 최소 대포알의 개수가 1 이니
 *       어떤 N 이 주어지더라도 N 개의 대포알 모두 사면체로 만들 수 있다
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>

using namespace std;

#define endl '\n'

// Set up : Global Variables
/* None */

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int N; cin >> N;

    // Process
    int dp[N+1]; /* dp[i] = i 개의 대포알을 사용해서 만들 수 있는 사면체의 최소 개수 */
    for (int i=0; i<=N; i++) {
        dp[i] = i; /* 사면체의 최소 개수가 1 이므로 dp[i] = i 로 초기화 */
    }

    /* 수열 A : 삼각형에 추가되는 한 줄
     * 수열 B : 길이 N 인 삼각형
     * 수열 C : 길이 N 을 밑면으로 하는 사면체 */
    int i, j, k; /* i = 수열 A, j = 수열 B, k = 수열 C */
    i = j = k = 1; /* 초기화 */
    /* 현재 다루고 있는 사면체를 이루는 대포알의 개수는 k 개 */
    while (k <= N) { /* k 가 N 보다 작으면 */
        /* k 를 이용하여 dp 갱신 */
        for (int n=1; n<=N; n++) {
            if (n >= k) {
                dp[n] = min(dp[n], dp[n-k]+1);
            }
        }

        /* 수열 A, B, C 갱신 */
        i += 1;
        j += i;
        k += j;
    }

    // Control : Output
    cout << dp[N] << endl;
}

// Helper Functions
/* None */
profile
이런 미친 게임을 봤나! - 옥냥이
post-custom-banner

0개의 댓글