[C++][프로그래머스] 카운트 다운 🔥

프로그래머스

 

📄 문제

프로그래머스 다트 협회에서는 매년마다 새로운 특수 룰으로 다트 대회를 개최합니다. 이번 대회의 룰은 "카운트 다운"으로 "제로원" 룰의 변형 룰입니다.
"카운트 다운"은 게임이 시작되면 무작위로 점수가 정해지고, 다트를 던지면서 점수를 깎아서 정확히 0점으로 만드는 게임입니다. 단, 남은 점수보다 큰 점수로 득점하면 버스트가 되며 실격 합니다.

다음 그림은 다트 과녁입니다.

 

다트 과녁에는 1 부터 20 까지의 수가 하나씩 있고 각 수마다 "싱글", "더블", "트리플" 칸이 있습니다. "싱글"을 맞히면 해당 수만큼 점수를 얻고 "더블"을 맞히면 해당 수의 두 배만큼 점수를 얻고 "트리플"을 맞히면 해당 수의 세 배만큼 점수를 얻습니다. 가운데에는 "불"과 "아우터 불"이 있는데 "카운트 다운" 게임에서는 구분 없이 50점을 얻습니다.

대회는 토너먼트로 진행되며 한 게임에는 두 선수가 참가하게 됩니다. 게임은 두 선수가 교대로 한 번씩 던지는 라운드 방식으로 진행됩니다. 가장 먼저 0점을 만든 선수가 승리하는데 만약 두 선수가 같은 라운드에 0점을 만들면 두 선수 중 "싱글" 또는 "불"을 더 많이 던진 선수가 승리하며 그마저도 같다면 선공인 선수가 승리합니다.

다트 실력에 자신 있던 종호는 이 대회에 출전하기로 하였습니다. 최소한의 다트로 0점을 만드는 게 가장 중요하고, 그러한 방법이 여러가지가 있다면 "싱글" 또는 "불"을 최대한 많이 던지는 방법을 선택해야 합니다.

목표 점수 target이 매개변수로 주어졌을 때 최선의 경우 던질 다트 수와 그 때의 "싱글" 또는 "불"을 맞춘 횟수(합)를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

 

📝 풀이

#include <string>
#include <vector>

using namespace std;

int dp[100001][2];

void check(int target) {
    // target - 60의 누적 개수와 target - 50의 누적 개수가 같다면?
    if (dp[target - 60][0] == dp[target - 50][0]) 
    {
        dp[target][0] = dp[target - 50][0] + 1; // 누적 개수 1 증가
        dp[target][1] = max(dp[target - 60][1], dp[target - 50][1] + 1); // max(target - 60의 값, target - 50의 값 + 1(불 사용))
    }
    // target - 60이 더 효율적이라면?
    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++) {
        /* 한 번에 끝내기 */
        // 싱글(20이하) 또는 불(50)로 끝내는 경우
        if (i == 50 || i <= 20) 
        {
            dp[i][0] = 1;
            dp[i][1] = 1; // 값 증가
        }
        // 60 이하의 3의 배수인 경우는 트리플로 가능
        else if (i <= 60 && i % 3 == 0) 
        {
            dp[i][0] = 1;
            dp[i][1] = 0; // 싱글,불이 아님
        }
        // 40 이하의 2의 배수인 경우에는 더블로 가능
        else if (i <= 40 && i % 2 == 0) 
        {
            dp[i][0] = 1;
            dp[i][1] = 0; // 싱글, 불이 아님
        }
        /* 블+싱글 조합으로 두 번에 끝내기 */
        // 50보다 크고 70 이하라면 2번(불 + 싱글)로 가능
        else if (i > 50 && i <= 70) 
        {
            dp[i][0] = 2;
            dp[i][1] = 2; // 불 + 싱글의 조합으로 2 증가
        }
        /* 나머지 두 번에 끝내기 */
        // 70보다 작은 수인경우, 아래의 두 조건으로 나눌 수 있음
        else if (i < 70) 
        {
            // 40 보다 작은 수라면, 싱글 2개로 조합 가능
            if (i < 40) 
            {
                dp[i][0] = 2;
                dp[i][1] = 2; // 싱글 2개
            }
            // 아니라면, 싱글 + 더블 조합으로 가능
            else 
            {
                dp[i][0] = 2;
                dp[i][1] = 1; // 싱글 1개
            }
        }
        // 71부터는 저장된 값을 고려하여 최선의 선택을 구하기
        else 
        {
            check(i);
        }
    }

    answer[0] = dp[target][0];
    answer[1] = dp[target][1];

    return answer;
}

• 싱글 또는 불을 최대한 많이 맞추면서, 맞추는 개수는 최소로 하여 정답을 구해야합니다.
• 이 문제는 dp를 활용하여 해결하였으며, 다음과 같은 규칙으로 접근할 수 있습니다.
  • dp를 [100001][2]로 선언하여 누적된  싱글 또는 불 / 다트의 개수를 저장합니다.
  • target이 50이거나, 20이하인경우에는 싱글 또는 불로 한번에 해결할 수 있습니다. 이 경우 dp에 누적 다트와 싱글/불 개수를 1로 설정할 수 있습니다.
  • target이 60 이하일 때, 3의 배수라면 1~20 값의 트리플로 해결할 수 있습니다. 이 경우 dp에 누적 다트는 1로, 싱글/불 개수는 0으로 합니다.
  • target이 40 이하일 때, 2의 배수라면 1~20 값의 더블로 해결할 수 있습니다.
  • 50보다 크고, 70 이하라면, 불 + 싱글의 조합 (50 + x)으로 해결할 수 있습니다. 이 경우에는  2, 2로 저장합니다.
  • 위 조건이 모두 아닐경우 70보다 작다면, 두가지의 경우를 고려할 수 있습니다.
    • 40보다 작다면, 두개의 싱글로 조합이 가능합니다.
    • 그렇지 않다면, 싱글 + 더블의 조합으로 가능합니다.
  • 위 모든 조건이 아니라면, 최선의 선택을 위해 함수를 통해 조건을 통해 값을 구합니다.
    • 60, 50을 사용하여 큰 값을 줄일 수 있습니다. 이 때, target-60의 횟수와 target-50의 누적 횟수가 같다면, 둘 중 불의 사용이 큰 개수를 [1]에 저장합니다.
    • target-60이 더 효율적이라면, 불을 사용하지 않고 누적 다트 수인 [0]에 저장합니다.
    • target-50이 더 효율적이라면, 불을 사용하여 누적 다트 수와 불 사용 수에 저장합니다.