프로그래머스 n + 1 게임 [Lv. 3] (C++)

프로그래머스

1 ~ N 사이의 수가 적힌 카드가 하나씩 있는 카드 뭉치와 coin을 이용하여 게임을 합니다.

라운드 시작 전에 N/3 개의 뽑아 모두 가진 채로 시작합니다.

각 라운드가 시작되면 카드 2장을 뽑으며 코인을 이용하여 카드를 구매 할 수 있습니다.

다음 라운드로 가기 위해서는 2장의 카드의 합이 N + 1인 카드 두 장을 내야만 합니다.

코인의 개수와 카드의 배열을 입력받을 때, 도달할 수 있는 최고 라운드는 어디인지 찾아주세요!

 

 

풀이 방법

이 문제를 풀기 위해서는 이 게임을 하는 플레이어의 입장에서 생각하면 안됩니다.

플레이어는 앞으로 나올 카드를 알 수 없으며, 지난 라운드에 뽑은 카드를 다시 구매할 수도 없습니다.

 

하지만 우리는 문제를 푸는 입장이기 때문에 앞으로 나올 카드도 알 수 있고, 구매하지 않은 카드들도 구매 했다 칠 수 있습니다.

여기서 핵심은 구매하지 않은 카드들도 구매 했다 칠 수 있는 부분입니다.

 

set<int> myDeck;
set<int> store;
int n = cards.size();

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

게임 시작시 공짜로 받는 나의 카드와 구매할 수 있는 카드를 다른 메모리에 저장해줍니다.

 

int round = 1;
for (int i = n/3; i < n; i += 2)
{
    store.insert(cards[i]);
    store.insert(cards[i+1]);

이후 매 라운드 마다, 상점에 살 수 있는 카드들을 등록해줍니다.

 

if (!CanCombine(myDeck, myDeck, n+1))

우선 내가 소지한 카드들로 조합을 만들 수 있는지 체크해줍니다.

 

bool CanCombine(set<int>& deck_A, set<int>& deck_B, int cost)
{
    for (int n : deck_A)
    {
        int target = cost - n;
        if (deck_B.find(target) != deck_B.end()){
            deck_A.erase(n);
            deck_B.erase(target);
            return true;
        }
    }
    return false;
}

set의 탐색 속도는 log N이기 때문에 최대 N * log N 의 속도로 계산이 가능합니다.

조합이 가능하다면 댁에서 카드들을 지워주며 true를 반환해줍니다.

불가능하다면 false를 반환합니다.

 

만약 내 손에 든 카드들로 조합이 불가능 하다면 상점에서 구매해야 합니다.

첫번 째로 생각해 볼 것은 코인을 하나 사용하는 나의 카드 + 구매 가능한 카드 조합입니다.

// 돈 없으면 종료
if (coin < 1)
    return round;

// 구매 가능한 카드 + 내 카드로 해결 가능한지 체크
if (!CanCombine(myDeck, store, n + 1))

만약 이 또한 불가능 하다고 한다면

코인을 두개 사용하여 구매 가능한 카드 + 구매 가능한 카드 조합을 찾아야합니다.

 

// 구매 가능한 카드들로 해결이 가능한지 체크
// 돈 없거나 조합을 찾지 못했다면 종료
if (coin < 2 || !CanCombine(store, store, n + 1))
    return round;

여기서도 찾지 못했다면 다음 라운드로 넘어갈 수 없기 때문에 종료합니다.

마지막으로 최종 round를 반환해주면 됩니다.

 

정답 코드

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

using namespace std;

bool CanCombine(set<int>& deck_A, set<int>& deck_B, int cost)
{
    for (int n : deck_A)
    {
        int target = cost - n;
        if (deck_B.find(target) != deck_B.end()){
            deck_A.erase(n);
            deck_B.erase(target);
            return true;
        }
    }
    return false;
}


int solution(int coin, vector<int> cards) {

    set<int> myDeck;
    set<int> store;
    int n = cards.size();
    
    for (int i = 0; i < n / 3; i++)
        myDeck.insert(cards[i]);
    
    int round = 1;
    for (int i = n/3; i < n; i += 2)
    {
        store.insert(cards[i]);
        store.insert(cards[i+1]);
        
        // 내 손 안에 든 카드로 해결이 가능한지 체크
        if (!CanCombine(myDeck, myDeck, n+1))
        {
            // 돈 없으면 종료
            if (coin < 1)
                return round;
            
            // 구매 가능한 카드 + 내 카드로 해결 가능한지 체크
            if (!CanCombine(myDeck, store, n + 1))
            {
                // 구매 가능한 카드들로 해결이 가능한지 체크
                // 돈 없거나 조합을 찾지 못했다면 종료
                if (coin < 2 || !CanCombine(store, store, n + 1))
                    return round;
                
                coin -= 2;
            }
            else
                coin--;
        }
        round++;
    }
    
    return round;
}