[Algorithm] Programmers :: 카운트 다운

https://school.programmers.co.kr/learn/courses/30/lessons/131129

프로그래머스

struct Node
{
    int dartsCount = 0x3f3f3f3f;
    int specialCount = 0x3f3f3f3f;
    int score = 0;
};
 
Node dp[100001];
 
vector<int> solution(int target) 
{
    vector<int> answer;
 
    queue<Node> q;
    q.push({ 0,0,target });
    dp[target] = { 0,0,target };
 
    while (!q.empty())
    {
        int curDartsCount = q.front().dartsCount;
        int curSpecialCount = q.front().specialCount;
        int curScore = q.front().score;
        q.pop();
 
        if (curScore == 0)
        {
            dp[0] = { curDartsCount,curSpecialCount,0 };
            continue;
        }
 
        bool visited[61] = { false };
 
        for (int i = 1; i <= 20; ++i)
        {
            int num = i;
            if (curScore - num >= 0 && (dp[curScore - num].dartsCount > curDartsCount+1 || (dp[curScore - num].dartsCount == curDartsCount+1 && dp[curScore - num].specialCount < curSpecialCount+1))) // 싱글
            {
                dp[curScore - num] = { curDartsCount + 1, curSpecialCount + 1, curScore - num };
                q.push({ curDartsCount + 1,curSpecialCount + 1,curScore - num });
            }
 
            num = i * 2;
            if (i >= 11 && !visited[num])
            {
                visited[num] = true;
 
                if (curScore - num >= 0 && (dp[curScore - num].dartsCount > curDartsCount + 1 || (dp[curScore - num].dartsCount == curDartsCount + 1 && dp[curScore - num].specialCount < curSpecialCount))) 
                {
                    dp[curScore - num] = { curDartsCount + 1, curSpecialCount, curScore - num };
                    q.push({ curDartsCount + 1,curSpecialCount,curScore - num });
                }
            }
 
            num = i * 3;
            if (i >= 7 && !visited[num])
            {
                visited[num] = true;
 
                if (curScore - num >= 0 && (dp[curScore - num].dartsCount > curDartsCount + 1 || (dp[curScore - num].dartsCount == curDartsCount + 1 && dp[curScore - num].specialCount < curSpecialCount))) 
                {
                    dp[curScore - num] = { curDartsCount + 1, curSpecialCount, curScore - num };
                    q.push({ curDartsCount + 1,curSpecialCount,curScore - num });
                }
            }
        }
 
        if (curScore - 50 >= 0 && (dp[curScore - 50].dartsCount > curDartsCount + 1 || (dp[curScore - 50].dartsCount == curDartsCount + 1 && dp[curScore - 50].specialCount < curSpecialCount)))
        {
            dp[curScore - 50] = { curDartsCount + 1, curSpecialCount + 1, curScore - 50 };
            q.push({ curDartsCount + 1,curSpecialCount+1,curScore - 50 });
        }
    }
 
    return { dp[0].dartsCount, dp[0].specialCount };
}

풀었던 3레벨들 중에선 상대적으로 쉬운 문제였다.

완전탐색에 DP를 섞을 줄 알면 되는 문제인데 사실상 문제설명 거의 그대로 구현하면 되는 정도의 난이도다.

 

최소의 다트횟수를 구하면서, 같은 횟수일 경우 최대의 불+싱글 카운트값을 업데이트해주면 된다.

싱글,더블,트리플에 대해 검사를 할때 동일 숫자가 나올 수 있으니 중복된 노드를 넣지 않는 코드를 작성해줘야 한다.

나같은 경우 불(50점)을 제외하고 나머지는 for문 하나로 끝내려고 저렇게 코드를 작성해봤다.