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

미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요!

 

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

프로그래머스

카운트 다운

문제

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

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

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

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

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

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

 

제한사항

• 1 ≤ target ≤ 100,000

 

풀이

입출력 예시

 

풀이

#include <string>
#include <vector>

using namespace std;

int result[2] = { 987654321, 987654321 };

void dfs(int all_count, int bull_single_count, int target) {
    if (target == 0) {
        if (result[0] > all_count) {
            result[0] = all_count;
            result[1] = bull_single_count;
        }
        else if (result[0] == all_count) {
            if (result[1] < bull_single_count) {
                result[1] = bull_single_count;
            }
        }

        return;
    }

    // 1. 한 번 만에 끝내기 가능한 경우 : 50점, 20이하의 수, 60 이하이면서 2와 3으로 나누어 떨어지는 수
    // 1-1. 싱글 or 불 1번으로 끝내는 경우(우선)
    if (target == 50 || target <= 20) {
        dfs(all_count + 1, bull_single_count + 1, 0);
    }
    // 1-2. 60 이하의 3의 배수인 경우는 트리플 한 번이면 게임 끝
    else if (target <= 60 && target % 3 == 0) {
        dfs(all_count + 1, bull_single_count, 0);
    }
    // 1-3. 40 이하의 2의 배수인 경우에는 더블 한 번이면 게임 끝
    else if (target <= 40 && target % 2 == 0) {
        dfs(all_count + 1, bull_single_count, 0);
    }
    // 2. 50보다 크고 70 이하라면 항상 2번(불 + 싱글)이 최선의 경우임
    else if (target > 50 && target <= 70) {
        dfs(all_count + 2, bull_single_count + 2, 0);
    }
    // 3. 그렇지도 않은데 70보다 작은 수들이면 2가지로 나뉨.
    // 어떤게 있지? 21 ~ 49 수들 중
    // 23, 25, 29, 31, 35, 37, 41, 43, 44, 46, 47, 49
    // 얘네들인데, 트리플이든 더블이든 일단 한번 하고 싱글 하나 하면 끝?
    // 근데 23, 25, 29, 31, 35, 37은 싱글 2번으로 가능한데?
    // 41, 43, 44, 46, 47, 49는 더블 1번 싱글 1번이면 되네?
    else if (target < 70) {
        // 3-1. 40 보다 작은 수들이면 싱글 2번이 최선의 경우
        if (target < 40) {
            dfs(all_count + 2, bull_single_count + 2, 0);
        }
        // 3-2. 아니라면 더블 1번 싱글 1번이 최선의 경우
        else {
            dfs(all_count + 2, bull_single_count + 1, 0);
        }
    }
    // 4. 그렇지도 않은 수들이면 (70보다 큰 수들)
    else {
        // 4-1. 20 트리플을 통해 진행한 점수
        dfs(all_count + 1, bull_single_count, target - 60);
        // 4-2. 불을 통해 진행한 점수
        dfs(all_count + 1, bull_single_count + 1, target - 50);
    }
}

vector<int> solution(int target) {
    vector<int> answer(2, 0);

    dfs(0, 0, target);

    answer[0] = result[0];
    answer[1] = result[1];

    return answer;
}

 

완전 탐색으로 풀면 시간 초과가 발생했다.

 

이 문제 처음 봤을 때는 target의 점수에서 0이 될 때 까지 반복해주는 문제라고 생각해서 골머리를 앓고 있었는데, 생각을 조금 바꿨다.

 

0점을 target점으로 만들어보자!

 

우선, 이 문제는 다이나믹 프로그래밍 문제였다. 그러니 문제 풀기 전에 항상 선언했던 dp 배열을 선언해준다.

이 dp 배열에는 각 점수들의 최선의 경우가 저장된다.

 

선언을 했으니 dp 배열의 초기 값들을 몇개 지정해줘야 한다. 그러기 위해 몇 가지 경우들을 나눠서 생각해본다.

 

1. 한 번 만에 target 점수를 맞추는 경우.

1-1. target이 1 이상 20 이하이거나, 50인 경우

 

이 경우는 싱글이나 불 한 번으로 게임을 끝낼 수 있다.

또한, 한 번만에 점수를 맞추는 경우 중, 가장 우선도가 높다.

던진 횟수가 같다면 싱글이나 불을 많이 던진 경우가 우선이라고 하기 때문이다.

 

즉, { 1, 1 } 이 된다.

 

1-2. target이 60 이하이면서 3의 배수인 경우

 

이 경우는 트리플 한 번으로 게임을 끝낼 수 있다.

39를 예로 들면, 13(트리플)로 39를 만들 수 있다.

 

즉, { 1, 0 } 이 된다.

 

1-3. target이 40 이하이면서 2의 배수인 경우

 

이 경우는 더블 한 번으로 게임을 끝낼 수 있다.

22를 예로 들면, 11(더블)로 22를 만들 수 있다.

 

즉, { 1, 0 } 이 된다.

 

 

2. target이 50보다 크고 70 이하인 경우

 

이 경우에는 항상 (불 + 싱글)의 조합인 경우가 최선이다.

63을 예로 들면, 50(불) + 13(싱글) 로 63을 만들 수 있다.

 

즉, { 2, 2 } 가 된다.

 

 

3. target이 70 보다 작은 경우

 

이 경우에 해당하는 수들은 23, 25, 29, 31, 35, 37, 41, 43, 44, 46, 47, 49 이다.

이 그룹은 2가지의 그룹으로 다시 나눌 수 있다.

 

3-1. 40 보다 작다면?

 

싱글 두 번이 최선의 경우이다.

23을 예로 들면, 20 + 3, 19 + 4, .... 등 많은 경우가 존재하지만 결국 싱글 2번으로 만들 수 있다.

 

즉, { 2, 2 } 가 된다.

 

3-2. 나머지 수들은?

 

더블 한 번과 싱글 한 번, 또는 트리플 한 번과 싱글 한 번을 섞으면 된다.

47을 예로 들면, 15(트리플) + 2(싱글)로 만들 수도 있고, 20(더블) + 7(싱글)로도 만들 수 있다.

경우가 여러개 존재하지만 결국 싱글 한 번에 트리플 한 번이다.

 

즉, { 2, 1 } 이 된다.

 

 

이제 마지막으로 위에 해당되지 않는 수들 즉,

target이 70보다 큰 경우를 찾아야한다.

 

경우의 수를 더 나눠서 생각해도 되겠지만 이러면 조건문이 끝없이 늘어날테고, 이 상태에서 답을 충분히 구할 수 있으니 여기서 멈춘다.

 

해답을 찾기 위해 간단한 예시로 target이 101일 때 최선의 경우를 찾는다고 하자.

즉, dp[101] 을 찾겠다는 소리다.

 

우리는 항상 최소 횟수로 target에 도달해야한다. 그러니, 가장 큰 수인 60(20 트리플)과 다음으로 큰 수인 50(불)을 더해가며 target에 도달해나갈 것이다.

 

60이 더 큰 수라서 60으로 계속 빼나가면 항상 최선이지 않겠나 싶겠지만, 우리는 던진 횟수가 똑같다면 (싱글 + 불)의 횟수가 더 많은 사람이 우승한다는 것을 알고 있다. 그래서 50을 맞추는 경우도 생각해야한다.

 

그렇다면, dp[101]은 다음 두가지의 경우 중 하나라고 할 수 있다.

 

dp[41]에서 20 트리플(60점)을 맞춘 경우와, dp[51]에서 불(50점)을 맞춘 경우이다.

 

즉, 둘 중에서 던진 횟수가 더 작은 경우를 택하거나, 둘 다 같다면 (싱글 + 불)을 맞춘 횟수가 더 많은 경우를 선택한다는 뜻이다.

 

정리하자면,

dp[i] = dp[i - 50]인 상태에서 불을 던지는 경우와 dp[i - 60]인 상태에서 20 트리플을 맞추는 경우 중 최선의 경우 선택

한다는 의미이다.

 

 

모든 경우를 구했으니, 코드로 옮겨준다.

 

항상 다이나믹 프로그래밍 문제는 날 어지럽게 만든다..

 

#include <string>
#include <vector>

using namespace std;

int dp[100001][2];

void set_best_case(int target) {
    if (dp[target - 60][0] == dp[target - 50][0]) {
        dp[target][0] = dp[target - 50][0] + 1;
        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++) {
        // 1. 한 번 만에 끝내기 가능한 경우
        // 1-1. 싱글 or 불 1번으로 끝내는 경우
        if (i == 50 || i <= 20) {
            dp[i][0] = 1;
            dp[i][1] = 1;
        }
        // 1-2. 60 이하의 3의 배수인 경우는 트리플 한 번이면 게임 끝
        else if (i <= 60 && i % 3 == 0) {
            dp[i][0] = 1;
            dp[i][1] = 0;
        }
        // 1-3. 40 이하의 2의 배수인 경우에는 더블 한 번이면 게임 끝
        else if (i <= 40 && i % 2 == 0) {
            dp[i][0] = 1;
            dp[i][1] = 0;
        }
        // 2. 50보다 크고 70 이하라면 항상 2번(불 + 싱글)이 최선의 경우임
        else if (i > 50 && i <= 70) {
            dp[i][0] = 2;
            dp[i][1] = 2;
        }
        // 3. 그렇지도 않은데 70보다 작은 수들이면 2가지로 나뉨.
        else if (i < 70) {
            // 3-1. 40 보다 작은 수들이면 싱글 2번이 최선의 경우
            if (i < 40) {
                dp[i][0] = 2;
                dp[i][1] = 2;
            }
            // 3-2. 아니라면 더블 1번 싱글 1번이 최선의 경우
            else {
                dp[i][0] = 2;
                dp[i][1] = 1;
            }
        }
        else {
            set_best_case(i);
        }
    }

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

    return answer;
}