카운트 다운

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

풀이(실패)

#include <string>
#include <vector>
#include <map>

using namespace std;

// 1. 가능한 다트 점수의 수.
// 2. target에서 빼면서 갯수 세기.
// 반례: 58, 기댓값: [2, 2](50, 8), 출력값: [2, 1](57, 1)

int Score[] = {60, 57, 54, 51, 50,
               48, 45, 42, 39, 36,
               33, 30, 27, 24, 21,
               20, 19, 18, 17, 16,
               15, 14, 13, 12, 11,
               10, 9, 8, 7, 6, 5, 4, 3, 2, 1};

vector<int> solution(int target) {
    vector<int> answer;
    map<int, int> Res;
    
    int i = 0, NumDart = 0;
    while(target != 0)
    {
        if(target >= Score[i])
        {
            target -= Score[i];
            Res[Score[i]]++;
            ++NumDart;
        }
        else
        {
            ++i;
        }
    }
    
    int BoolAndSingle = 0;
    for(int i = 1; i <= 20; ++i)
    {
        BoolAndSingle += Res[i];
    }
    BoolAndSingle += Res[50];
    
    answer.push_back(NumDart);
    answer.push_back(BoolAndSingle);
    
    return answer;
}

---

풀이(실패)

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int target) {
    vector<int> answer(2);
    
    int NumThrow = 0;
    NumThrow += target / 60;
    target %= 60;
    
    if(target % 3 == 0)
    {
        if(target != 0)
        {
            NumThrow++;
        }
        answer[0] = NumThrow;
        return answer;
    }
    
    answer[0] = NumThrow;
    if(target >= 51 && target <= 59)
    {
        answer[0] += 2;
        answer[1] = 2;      // Bool 1번, Single 1번.
    }
    else if(target == 50)
    {
        ++answer[0];
        answer[1] = 1;      // Bool 1번.
    }
    else if(target >= 41)
    {
        ++answer[0];        // 20 더블 1번.
        answer[1] = 1;      // Single 1번.
    }
    else if(target == 40)
    {
        ++answer[0];        // 20 더블 1번.
    }
    else if(target >= 21 && target <= 39)
    {
        if(target % 2 == 0)
        {
            ++answer[0];    // 더블 1번.
        }
        else
        {
            answer[0] += 2;
            answer[1] = 2;  // Single 2번.
        }
    }
    else if(target <= 20)
    {
        ++answer[0];
        answer[1] = 1;      // Single 1번.
    }
    
    return answer;
}

---

출처: https://ggjjdiary.tistory.com/219

풀이

1. 70까지의 Dp 배열을 만든다.
2. 70 초과의 i에 대해 Dp 배열을 채워가며 target까지 구한다.

#include <string>
#include <vector>

using namespace std;

// 던진 횟수, 불 || 싱글 횟수.
int Dp[100001][2];

void SetBestCase(int target)
{
    // 던진 횟수 우선.
    if(Dp[target - 60][0] == Dp[target - 50][0])
    {
        Dp[target][0] = Dp[target - 60][0] + 1;
        // target - 60에서 60 트리플을 맞춘 경우, target - 50에서 50 불을 맞춘 경우.
        Dp[target][1] = max(Dp[target - 60][1], Dp[target - 50][1] + 1);
    }
    else if(Dp[target - 60][0] < Dp[target - 50][0])
    {
        Dp[target][0] = Dp[target - 60][0] + 1;
        Dp[target][1] = Dp[target - 60][1];
    }
    else
    {
        Dp[target][0] = Dp[target - 50][0] + 1;
        Dp[target][1] = Dp[target - 50][1] + 1;
    }
}

vector<int> solution(int target) {
    vector<int> answer(2, 0);
    
    for(int i = 1; i <= target; ++i)
    {
        if(i == 50 || i <= 20)
        {
            Dp[i][0] = 1;   // 1번 던짐.
            Dp[i][1] = 1;   // 무조건 불 || 싱글임.
        }
        else if(i <= 60 && i % 3 == 0)
        {
            Dp[i][0] = 1;   // 1번 던짐.
            Dp[i][1] = 0;   // 트리플 1번.
        }
        else if(i <= 40 && i % 2 == 0)
        {
            Dp[i][0] = 1;   // 1번 던짐.
            Dp[i][1] = 0;   // 더블 1번.
        }
        else if(i > 50 && i <= 70)
        {
            Dp[i][0] = 2;   // 불 + 싱글.
            Dp[i][1] = 2;   // 불 + 싱글. 
        }
        else if(i < 70)
        {
            if(i < 40)
            {
                Dp[i][0] = 2;   // 싱글 2번.
                Dp[i][1] = 2;   // 싱글 2번.
            }
            else
            {
                Dp[i][0] = 2;   // 싱글 1번, 더블 1번.
                Dp[i][1] = 1;   // 싱글 1번.
            }
        }
        else
        {
            SetBestCase(i);
        }
    }
    
    answer[0] = Dp[target][0];
    answer[1] = Dp[target][1];
    
    return answer;
}