[코딩테스트] [프로그래머스] n + 1 카드게임

문제

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

---

풀이

0. 동전을 최대한 적게 소모하면서 라운드를 진행해야 하므로, 동전 소모 개수에 따라서 분기한다.
   0-1. 동전을 0개(zeroCoinPairs), 1개(oneCoinPairs), 2개(twoCoinPairs) 소모하고 다음 라운드로 넘어갈 수 있는 경우의 수를 변수로 선언한다.
   0-2. 손에 들고 있는 카드 체크용 벡터(hand), 카드 뭉치에 남아있는 카드 체크용 벡터(reserve)를 선언한다.

1. n/3개의 카드를 hand에 넣어준다. 이때, hand에 있는 카드끼리 조합해 n+1이 된다면 동전을 0개 소모하고 다음 라운드로 넘어갈 수 있기에 zeroCoinPairs를 증가시킨다.

2. n/3부터 카드 뭉치를 순회하며 2개의 카드(draw1, draw2)를 꺼낸다.
   2-1. reserve에 draw1, draw2 카드를 넣어주고, 해당하는 동전 소모 경우의 수를 1씩 증가시켜준다.
   2-2. 동전을 가장 적게 소모하는 경우의 수부터 확인하며, 라운드 횟수를 늘리고 동전 소모 경우의 수를 1씩 감소시킨다.
   2-3. 동전을 0개, 1개, 2개를 소모하는 경우의 수에 모두 포함되지 않는 경우 해당 라운드에서 게임이 종료되므로 반복문을 종료한다.

2-4. round를 반환한다.

---

코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(int coin, vector<int> cards)
{
    vector<bool> hand(1000, false);
    vector<bool> reserve(1000, false);
    
    int cardCount = cards.size();
    int zeroCoinPairs = 0, oneCoinPairs =0, twoCoinPairs =0;
    
    for(int i=0; i<cards.size() / 3; i++)
    {
        hand[cards[i]] = true;
        if(hand[cards[i]] && hand[cardCount + 1 - cards[i]])
        {
            zeroCoinPairs++;
            hand[cardCount + 1 - cards[i]] = false;
        }
    }
    
    int round = 1;
    for(int i=cards.size() / 3; i<cardCount; i+=2)
    {
        int draw1 = cards[i];
        int draw2 = cards[i+1];
        
        reserve[draw1] = true;
        reserve[draw2] = true;
        
        if(reserve[draw1] && hand[cardCount + 1 - draw1])
        {
            oneCoinPairs++;
            reserve[draw1] = false;
            hand[cardCount + 1 - draw1] = false;
        }
        if(reserve[draw2] && hand[cardCount + 1 - draw2])
        {
            oneCoinPairs++;
            reserve[draw2] = false;
            hand[cardCount + 1 - draw2] = false;
        }
        if(reserve[draw1] && reserve[cardCount + 1 - draw1])
        {
            twoCoinPairs++;
            reserve[draw1] = false;
            reserve[cardCount + 1 - draw1] = false;
        }
        if(reserve[draw2] && reserve[cardCount + 1 - draw2])
        {
            twoCoinPairs++;
            reserve[draw2] = false;
            reserve[cardCount + 1 - draw2] = false;
        }
        
        if(zeroCoinPairs > 0)
        {
            zeroCoinPairs--;
            round++;
        }
        else if(oneCoinPairs > 0 && coin >= 1)
        {
            oneCoinPairs--;
            coin--;
            round++;
        }
        else if(twoCoinPairs > 0 && coin >= 2)
        {
            twoCoinPairs--;
            coin -= 2;
            round++;
        }
        else
            break;
    }
    
    return round;
}