C++:: 프로그래머스 < 카운트 다운 >

처음에는 queue를 사용하여 풀라하였는데 시간초과가 났고, 생각을 해보니 굳이 queue로 풀지않고 비슷한 방식으로 dp처럼 사용해 풀어도 되겠다는 생각을 하였다.
문제자체는 크게 어렵지않다.

queue를 사용한 풀이 (시간 초과 코드)

#include <string>
#include <vector>
#include <queue>
using namespace std;

vector<int> solution(int target) {
    vector<pair<int, int>> cnts(target+1, {0,0});
    queue<int> q;
    q.push(target);
    while (!q.empty()) {
        int cur = q.front(), nextScore;
        q.pop();
        for (int i = 1; i <= 20; i++) {
            for (int j = 1; j <= 3; j++) {
                nextScore = cur - i*j;
                if (nextScore < 0) continue ;
                if (cnts[nextScore].first && cnts[nextScore].first <= cnts[cur].first) continue ;
                if (cnts[nextScore].first == cnts[cur].first + 1 && cnts[nextScore].second > cnts[cur].second) continue ;
                cnts[nextScore].first = cnts[cur].first + 1;
                if (j == 1) cnts[nextScore].second = cnts[cur].second + 1;
                else cnts[nextScore].second = cnts[cur].second;
                q.push(nextScore);
            }
        }
        nextScore = cur - 50;
        if (nextScore >= 0 && cnts[nextScore].first && cnts[nextScore].first > cnts[cur].first && cnts[nextScore].second <= cnts[cur].second) {
            cnts[nextScore].first = cnts[cur].first + 1;
            cnts[nextScore].second = cnts[cur].second + 1;
            q.push(nextScore);
        }
    }
    return {cnts[0].first, cnts[0].second};
}

dp방식 풀이코드

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

bool isAbleScore(int nextScore, int cur, vector<pair<int, int>> *cnts) {
	// 현재 점수에서 다트를 맞춘점수를 뺀 nextScore에 대한 판별
    // 1. 버스트
    if (nextScore < 0) return false ;
    // 2. 다트 횟수가 같거나 더많으면
    if ((*cnts)[nextScore].first && (*cnts)[nextScore].first <= (*cnts)[cur].first) return false ;
    // 3. 다트횟수가 하나 적지만 싱글과 불을 맞춘 횟수가 적다면
    if ((*cnts)[nextScore].first == (*cnts)[cur].first + 1 && (*cnts)[nextScore].second > (*cnts)[cur].second) return false ;
    return true;
}

vector<int> solution(int target) {
    vector<pair<int, int>> cnts(target+1, {0,0});
    for (int cur=target; cur>0; cur--) {
        int nextScore;
        for (int score=1; score<=20; score++) {
            for (int i=1; i<=3; i++) {// 싱글, 더블, 트리플 점수
                nextScore = cur - score*i;
                if (!isAbleScore(nextScore, cur, &cnts)) continue ;
                cnts[nextScore].first = cnts[cur].first + 1;// 다트 횟수 ++
                if (i == 1) cnts[nextScore].second = cnts[cur].second + 1;// 싱글이면
                else cnts[nextScore].second = cnts[cur].second;
            }
        }
        nextScore = cur - 50;// 불 맞추는 경우
        if (!isAbleScore(nextScore, cur, &cnts)) continue ;
        cnts[nextScore].first = cnts[cur].first + 1;
        cnts[nextScore].second = cnts[cur].second + 1;
    }
    return {cnts[0].first, cnts[0].second};
}