n + 1 카드 게임 [Lv. 3] (C++)

프로그래머스

카드 뭉치와 동전을 이용한 게임을 진행합니다.

게임을 시작할 때 n / 3 장의 카드를 뽑아 모두 가지고 매 라운드 2장의 카드를 뽑으며 

각 카드당 하나의 코인씩 지불하여 가져올 수 있습니다. 라운드가 끝나면 두 카드의 합이 [카드의 총 개수 + 1]이 되는 카드를 내고 다음 라운드로 넘어갑니다. 낼 카드가 없다면 게임은 종료됩니다.

이 문제는 최적의 방법으로 게임을 진행할 때 얼마나 오래 게임을 할 수 있는지 계산하는 문제입니다.

 

풀이 방법

경우의 수는 총 3가지로 생각해 볼 수 있습니다.

1. 카드를 사지 않을 경우 (이 때는 내 손에 있는 카드를 냅니다)

2. 카드를 하나 구매할 경우 (내 손의 카드 하나와 구매한 카드 하나를 냅니다)

3. 카드를 두개 모두 구매할 경우 (구매한 카드를 모두 내 다음 라운드로 갑니다)

 

DFS로 모든 경우의 수를 탐색하면 정답을 찾을 수는 있겠지만

속도 문제에 의해 문제를 해결할 수는 없습니다.

 

라운드라는 키워드와 3가지 경우의 수에 의해 이 문제를 여러 경우의 수를 탐색해야 하는

다이나믹 프로그래밍, DFS, BFS 등으로 생각할 수 있지만 자세히 들여다 보면 그렇지 않습니다.

 

이 게임을 직접 한다고 했을 때 이런 말을 가장 많이 하게 될겁니다.

"아! 이전 라운드에서 그 카드를 샀어야 했는데!!"

 

실제 게임에서는 아까 버린 그 카드를 다시 가져올 수 없지만

여기서는 그냥 샀다 치면 됩니다. 그렇기 때문에 매 라운드에서 살 수 있는 카드를 따로 보관해주고

필요할 때 "그때 샀다 치자!"를 해주면 최고 라운드 까지 쉽게 도달 할 수 있습니다.

 

코드 설명

손에 들고 시작하는 카드와, 이후 매 라운드 마다 살 수 있는 카드를 따로 관리합니다.

set<int> hands, draws;

- set으로 하는 이유는 빠른 탐색, 삭제가 가능하기 때문입니다.

 

for (int i = 0; i < size / 3; i++)
        hands.insert(cards[i]);

1/3을 가지고 시작합니다.

 

for (int i = size / 3; i < size; i+=2)
{
	// 매 라운드 살 수 있는 카드를 draws에 넣어 관리합니다.
    draws.insert(cards[i]); 
    draws.insert(cards[i+1]);

    // 손에 있는 패로 목표 수를 만들 수 있는지
    if (MatchCards(hands, hands, size+1)){
        // 코인 소모 없음
    }
    // 손에 있는 패 + 살 수 있는 패로 가능한지
    else if (coin >= 1 && MatchCards(hands, draws, size+1)){
        coin -= 1;
    }
    // 살 수 있는 패로 낼 수 있는지
    else if (coin >= 2 && MatchCards(draws, draws, size+1)){
        coin -= 2;
    }
    // 모두 불가능하다면 게임 종료
    else
        break;

    answer++;
}

 

카드 뭉치를 비교하여 (MatchCards 함수) 낼 수 있는지 체크합니다.

 

bool MatchCards(set<int>& cards1, set<int>& cards2, int target)
{
    for (int a : cards1)
    {
        auto it = cards2.find(target - a);
        if (it != cards2.end())
        {
            cards1.erase(a);
            cards2.erase(*it);
            return true;
        }
    }
    return false;
}

 set이 이진 트리구조 이기 때문에 nLogn 의 속도이지만 

이중 for문으로 N*N의 속도로 만들어도 문제 풀이가 가능했습니다.

 

전체 코드

#include <string>
#include <vector>
#include <set>

using namespace std;

bool MatchCards(set<int>& cards1, set<int>& cards2, int target)
{
    for (int a : cards1)
    {
        auto it = cards2.find(target - a);
        if (it != cards2.end())
        {
            cards1.erase(a);
            cards2.erase(*it);
            return true;
        
        }
    }
    
    return false;
}

int solution(int coin, vector<int> cards) 
{
    set<int> hands, draws;
    int answer = 1, size = cards.size();
    
    for (int i = 0; i < size / 3; i++)
        hands.insert(cards[i]);
    
    for (int i = size / 3; i < size; i+=2)
    {
        draws.insert(cards[i]);
        draws.insert(cards[i+1]);
        
        // 손에 있는 패로 목표 수를 만들 수 있는지
        if (MatchCards(hands, hands, size+1))
        {
            // 코인 소모 없음
        }
        else if (coin >= 1 && MatchCards(hands, draws, size+1))
        {
            coin -= 1;
        }
        else if (coin >= 2 && MatchCards(draws, draws, size+1))
        {
            coin -= 2;
        }
        else
            break;
        
        answer++;
    }
    
    
    return answer;
}