백준 1660번 캡틴 이다솜

문제 링크입니다: https://www.acmicpc.net/problem/1660

언제나처럼 Top-Down 방식으로 접근했지만 메모리 에러가 발생했습니다.

접근 방법은 Bottom-Up 방식과 유사하게 했지만 재귀호출을 너무 많이 하여 오류가 뜨는 것 같습니다.

#include <iostream>

#include <algorithm>

#include <cstring> //memset

using namespace std;

 

const int MAX = 300000 + 1;

//cannon[121] = 302621

const int CANNONMAX = 121 + 1;

 

int N;

int cannon[CANNONMAX];

int cache[MAX];

 

void preCalculate(void)

{

        //사면체 각 줄에 필요한 대포 개수 구하고

        for (int i = 1; i < CANNONMAX; i++)

                 cannon[i] = cannon[i - 1] + i;

        //사면체에 필요한 대포 개수 구한다

        for (int i = 2; i < CANNONMAX; i++)

                 cannon[i] += cannon[i - 1];

}

 

int minTetrahedron(int N)

{

        if (N <= 0)

                 return 0;

 

        int &result = cache[N];

        if (result != -1)

                 return result;

 

        int start;

        //사면체에 필요한 대포알 수가 N보다 작거나 같을 경우 찾고

        for (start = CANNONMAX - 1; start > 0; start--)

                 if (N - cannon[start] >= 0)

                         break;

 

        //start에서부터 하나씩 줄여가며(cannon[start]는 사면체에 필요한 대포알 수)

        //최소 사면체 개수를 구한다

        result = 1 + minTetrahedron(N - cannon[start]);

        for(int i=1; i<start; i++)

                 result = min(result, 1 + minTetrahedron(N - cannon[i]));

 

        return result;

}

 

int main(void)

{

        cin >> N;

 

        preCalculate();

 

        memset(cache, -1, sizeof(cache));

        cout << minTetrahedron(N) << endl;

        return 0;

}

Top-Down 방식이 실패했기 때문에 자신이 없는 Bottom-Up 방식으로 코드를 작성했는데 제 기준에서는 역시 Top-Down 방식보다 어려웠던 것 같습니다.

아무래도 코드를 봤을 때 직관적이지 않기 때문에 그런 것 같은데 앞으로는 Bottom-Up 방식도 연습해봐야할 것 같습니다.

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

 

const int MAX = 300000 + 1;

 

int N;

vector<int> tetrahedron;

vector<int> minTetrahedron;

 

void preCalculate(void)

{

        int num = 1, total = num;

        tetrahedron.push_back(num);

        //각 사면체에 필요한 대포알 수 구함

        while (1)

        {

                 num++;

                 total += (num*(num + 1) / 2);

                 if (total >= MAX)

                         break;

                 tetrahedron.push_back(total);

        }

 

        //벡터 범위 설정

        minTetrahedron.resize(MAX);

        for (int i = 1; i < MAX; i++)

                 minTetrahedron[i] = MAX;

        //인덱스가 사면체에 필요한 개수일 경우 하나의 사면체로 충분

        for (int i = 0; i < tetrahedron.size(); i++)

                 minTetrahedron[tetrahedron[i]] = 1;

}

 

int main(void)

{

        cin >> N;

 

        preCalculate();

 

        for (int i = 0; i < tetrahedron.size(); i++)

                 for (int j = tetrahedron[i]; j <= N; j++)

                         //(i+1)번 쨰 사면체를 추가하지 않을 경우, 추가할 경우

                         minTetrahedron[j] = min(minTetrahedron[j], 1 + minTetrahedron[j - tetrahedron[i]]);

 

        cout << minTetrahedron[N] << endl;

        return 0;

}

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~