[1일 1알고] 카운트 다운

https://school.programmers.co.kr/learn/courses/30/lessons/131129?language=cpp

프로그래머스

 

해당 문제는 특정 점수를 최소회수로 도달하는 방법을 찾는 문제입니다.

 

문제의 결을 보면 코인 혹은 배낭 문제와 비슷한 dp문제라고 생각이 드실겁니다. 

 

dp문제가 언제나 그렇듯 점화식을 세우고 dp배열을 어떻게 설정할지가 가장 중요하게 되는데요

---

dp의 index는 점수, dp의 value는 필요한 횟수, 싱글or불의 횟수로 지정하는 것이 타당해 보입니다.

 

그리고 미리 점수를 계산하기 위한 array를 만들어야 이를 통해 비교하고 dp배열을 갱신해 나갈 것입니다.

---

#include <string>
#include <vector>

using namespace std;

// 다트 게임 -> 제로원의 변형 룰인 카운트 다운 사용
// 무작위 점수를 깎아가며 0점으로 만드는 게임
// 0보다 작아진다면(-) 버스트가 되며 실격

// 최선의 경우 던질 다트 수와 그 때의 싱글, 불을 최대화

// ex 150 60 60 31 50 50 50 

vector<int> solution(int target) {

    vector<pair<int, int>> scores; // 점수, 싱글(불)
    scores.push_back({ 50, 1 });

    for (int i = 1; i <= 20; ++i)
    {
        scores.push_back({ i, 1 });
        scores.push_back({ i*2, 0 });
        scores.push_back({ i*3, 0 });
    }

    vector<pair<int, int>> dp(target+1, {target+1,0}); // (횟수, 싱글(불))
    dp[0] = { 0, 0 };
    for (int i = 0; i <= target; ++i)
    {
        for (auto score : scores)
        {
            if (i - score.first >= 0)
            {
                if (dp[i].first == dp[i - score.first].first + 1)
                {
                    dp[i].second = max(dp[i].second, 
                        dp[i - score.first].second + score.second);
                }
                else if (dp[i].first > dp[i - score.first].first + 1)
                {
                    dp[i].first = dp[i - score.first].first + 1;
                    dp[i].second = dp[i - score.first].second + score.second;
                }
            }
        }
    }


    return { dp[target].first, dp[target].second };
}

사실 이번 문제에서 dp가 생각이 나지않아 애먹었네요