카운트 다운 [Lv. 3] (C++)

코딩테스트 연습 - 카운트 다운 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

다트 협회에서 특수 룰 다트 대회를 개최하였습니다.

최소한의 횟수로 목표 점수에 도달해야하며 횟수가 같을 경우 싱글, 볼 횟수에 따라 등수를 나눕니다.

목표 점수를 입력받을 때 도달할 수있는 최소 다트 횟수와 싱글, 볼 횟수를 찾아주세요

 

풀이 방법

다트 횟수, 싱글 + 볼 횟수가 같은 경우의 수는 셀 수 없이 많이 있습니다.

그런데 이러한 것들을 모두 알 필요는 없습니다. (점수만 알면 됩니다)

그렇기 때문에 다트 횟수, 싱글 + 볼 횟수를 기록하여 중복 계산하는 경우를 줄여주어야합니다.

// target에 대해서 이미 계산한적 있다면 return
if (dp[target].first > 0)
        return dp[target];

 

다트를 던지는 경우의 수는 4개입니다.

(싱글, 볼, 트리플, 더블) 이 모든 경우에 대해서 탐색하는 DFS 방식으로 하면 되고

위에서 말한 중복 계산을 피하는 방식으로 시간초과를 피하면됩니다.

 

정답 코드

 

#include <string>
#include <vector>
#include <queue>

using namespace std;
const int MAX = 1000000000;
vector<pair<int, int>> dp;

// priority_queue용 비교 함수
struct compare
{
    bool operator()(pair<int, int>& a, pair<int, int>& b)
    {
        if (a.first == b.first)
            return a.second < b.second;
        return a.first > b.first;
    }
};

// pair 더해주는 함수
pair<int, int> ADD_PAIRS(pair<int, int>a, pair<int, int>b)
{
    return {a.first + b.first, a.second + b.second};
}

pair<int, int> DFS(int target)
{ // 끝에 도달했다면 return
    if (target == 0)
        return {0, 0};
    
    // 이미 계산된 적이 있다면 return
    if (dp[target].first > 0)
        return dp[target];
    
    // 모든 경우의 수 중 최적의 수를 찾기 위한 priority_queue
    // 단순 계산해도 상관X
    priority_queue<pair<int, int>, vector<pair<int, int>>, compare> q;
    
    // 트리플 +  60 이상의 큰 수
    if (target > 20)
    {	// 60 보다 작으면 트리플 맞춰서 남은 수, 크면 - 60
        int next = target <= 60 ? target % 3 : target - 60;
        q.push(ADD_PAIRS(DFS(next), {1, 0}));
    }
    
    // 더블
    if (target > 20 && target <= 40)
        q.push(ADD_PAIRS(DFS(target % 2), {1, 0}));
    
    // 볼
    if (target >= 50)
       q.push(ADD_PAIRS(DFS(target - 50), {1, 1}));
    
    // 싱글
    int next = max(0, target - 20);
    q.push(ADD_PAIRS(DFS(next), {1, 1}));

	// 최적의 값을 저장
    return dp[target] = q.top();
}

vector<int> solution(int target) {
    dp.resize(target+1, {-1, -1});
    DFS(target);
    return {dp[target].first, dp[target].second};
}