백준 2839번 설탕 배달

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

간단한 수학문제인줄 알고 풀었는데 알고보니 동적계획법 문제였습니다.

동적계획법을 이용하지 않을 경우 시간초과가 발생하므로 메모이제이션을 하는 것이 핵심이였습니다.

#include <iostream>

#include <cstring> //memset

#include <algorithm>

using namespace std;

 

const int INF = 987654321;

const int MAX = 5000;

 

int cache[MAX + 1];

 

int leastBag(int N)

{

        //기저 사례

        if (N == 0) //정확한 양일 경우

               return 0;

        if (N < 0) //배달할 수 없는 경우

               return INF;

        int &result = cache[N];

        if (result != -1)

               return result;

 

        result = 0;

        result = 1 + min(leastBag(N - 3), leastBag(N - 5));

        return result;

}

 

int main(void)

{

        int N;

        cin >> N;

 

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

 

        int result = leastBag(N);

        if (result >= INF) //INF에서 더해지므로

               cout << -1 << endl;

        else

               cout << result << endl;

        return 0;

}

개발환경:Visual Studio 2017

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