[BOJ 백준] 1660번 : 캡틴 이다솜 (C++)

[BOJ 백준] 1660번 : 캡틴 이다솜 (C++)

목차

• 01. 개요
• 02. 접근 방식
• 03. 정답 코드
• 04. 마무리

---

01. 개요

출처

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

 

문제

 

입력

 

출력

 

예시

 

 

---

02. 접근 방식

 

요약

DP 사용하기

1. 삼각형의 한 면에 대한 대포알 개수 구하기 ( fn] = f[n-1] + n )

2. 1번 과정을 통해 사면체의 대포알 개수 구하기 ( g[n] = g[n-1] + f[n] )

3. 현재 사용할 수 있는 대포알이 x개( x≤n ) 일 때, ( h[n] = min(h[n], h[n-x] + 1) )

4. 3번 과정을 대포알 1개일 때부터 n개일 때까지 검사를 진행하면, h[n]은 사면체의 최소 개수를 구할 수 있음

과정

먼저, 사면체를 구성하는 삼각형의 대포알 개수를 크기에 따라 구해야 합니다.

 

삼각형을 구성하는 대포알 개수는 높이가 1 증가할 때마다, 높이의 값만큼 추가됩니다.

 

사면체를 구성하는 대포알 개수는 사면체의 높이가 1층씩 커질 때마다, 사면체 제일 밑에 삼각형을 하나 더 추가하면 됩니다.

즉, 사면체 제일 밑에 현재 사면체의 층과 같은 높이(줄)를 가지는 삼각형을 추가하면 됩니다.

 

 

 

미리 구한 사면체의 높이에 따른 대포알 개수로 대포알이 n개일 때, 최소 사면체의 개수를 구하면 됩니다.

 

따라서, 아래와 같은 점화식이 성립됩니다.

h[n] = min(h[n], h[n-x] + 1) 

 

주의점

점화식을 사용할 때, 반드시 x가 n을 초과하지 않는 모든 사면체에 대해서 검사를 해야 합니다.

이는 n과 가장 가까운 x가 항상 사면체를 구성하는 최솟값을 만족하지 않기 때문입니다.

 

---

03. 정답 코드

// 골드 5 - 1660번 : 캡틴 이다솜
// 작성자 : free4760(jeonghoe22)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    // 입출력 최적화
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    // N개 대포알
    int N;
    cin >> N;

    vector<int> tastrahedrons;
    tastrahedrons.push_back(1);

    int triangle = 1;
    int seq = 2;
    int new_tastrahedron = 1;
    bool b_continue = true;
    // 사면체 개수 정보 미리 입력
    while(b_continue)
    {
        // 사면체 만드는 방법 = 새롭게 넓어진 삼각형 + 바로 직전 사면체
        triangle += seq;
        new_tastrahedron = triangle + tastrahedrons[tastrahedrons.size()-1];
        seq++;

        if(new_tastrahedron <= 300000)
        {
            tastrahedrons.push_back(new_tastrahedron);
        }
        // 30만 개 이상은 필요 없으므로 무시
        else
        {
            b_continue = false;
        }
    }

    // 사면체 개수 제작
    int result = 300000;
    vector<int> cases(N+1);

    // 1개짜리만 사용할 때, 사면체 개수 넣기
    for(int i = 0; i < N+1; i++)
    {
        cases[i] = i;
    }

    // 목표 대포알 개수까지 반복
    for(int i = 1; i < N+1; i++)
    {
        // 사면체 수량만큼 반복
        for(const int& tastrahedron : tastrahedrons)
        {
            // 사면체 개수가 유효 대포알보다 많은 경우도 무시
            if(tastrahedron > i) break;
            // 현재 목표 개수에서 사면체를 사용하는 경우가 더 나은 경우
            // 1개를 추가하는 이유 : 여러 개를 사용할 때는 이미 더 작은 사면체로 갱신됨
            cases[i] = min(cases[i], cases[i-tastrahedron] + 1);
        }
    }

    cout << cases[N] << "\n";
}

 

---

04. 마무리

처음에는 대포알 개수가 n개일 때, n과 가장 가까운 사면체가 항상 사면체의 최솟값을 유지한다고 생각해 틀렸었습니다.

이러한 조건을 한 번에 생각할 수 있도록 더 노력해야겠습니다.

 

---

 

읽어주셔서 감사합니다.

틀린 내용 지적은 언제나 환영입니다!