프로그래머스 - 카운트 다운 [C++]

이 문제는 다이나믹 프로그래밍으로 풀었다.

 

이 문제는 싱글, 더블, 트리플, 불 네 가지의 점수를 파악하고 그 중 겹치는 것이 있으면 싱글, 불로 카운팅하는 것이 중요하다. 

2의 경우 2 싱글일 수도 있지만, 1 더블일 수도 있다. 이 경우 2 싱글로 판단하도록 하는 것이다.

 

시간 복잡도의 경우 100,000 * 43 = 4,300,000 이므로 충분히 1초 안에 풀 수 있다.

다이나믹 프로그래밍에서 바텀업 방식이 탑다운 방식보다 확실히 빠른 것 같다. 또한 가끔 바텀업으로 생각하는게 더 쉬운 경우도 있었다. dp 문제를 풀 때 항상 탑다운으로 생각했는데, 바텀업으로도 생각해봐야할 것 같다.

#include <string>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;

#define INF 1000000000
#define MAX 100000

vector<int> scores = {
                        1,2,3,4,5,6,7,8,9,10,11,12,13,14,
                        15,16,17,18,19,20,21,
                        22,24,26,27,28,30,32,33,34,36,38,
                        39,40,42,45,48,50,51,54,57,60
                     };
pair<int, int> dp[MAX + 300];

bool singleOrBool(int dart)
{
    if ((1 <= dart && dart <= 20) || dart == 50)
    {
        return true;
    }
    return false;
}

void init()
{
    for (int i = 0; i < MAX + 300; i++)
    {
        dp[i] = {INF, INF};
    }
}

vector<int> solution(int target) 
{
    init();
    dp[0] = {0, 0};
    for (int i = 0; i <= target; i++)
    {
        int presentDart = dp[i].first;
        int presentSob = dp[i].second;
        for (int score : scores)
        {
            int nextDart = presentDart + 1;
            int nextSob = presentSob;
            if (singleOrBool(score))
            {
                nextSob++;
            }
            if (dp[i + score].first > nextDart)
            {
                dp[i + score] = {nextDart, nextSob};
            }
            else if (dp[i + score].first == nextDart && dp[i + score].second < nextSob)
            {
                dp[i + score] = {nextDart, nextSob};
            }
        }
    }
    vector<int> answer = {dp[target].first, dp[target].second};
    return answer;
}