n + 1 카드게임

까다로운 그리디 문제다. 그냥 문제 설명만 읽고 그대로 구현하려고 했다가는 미궁에 빠질 수 밖에 없을거같다.

일단 이 문제의 테마는 #그리디, #시뮬레이션 이다. 다른 DP나 특별한 알고리즘이 들어간게 아니고 어떻게 하면 더 그리디하게 문제를 맞출 수 있을까 고민해봐야한다.

이 문제를 접근하려고 별 방법을 다 생각해본거 같다. Queue 도 생각해봤고 등등. 그렇지만 문제 설명을 그대로 받아들이고 구현하려고 했던게 문제였던거 같다.

(문제 설명 생략) 카드를 그리디 하게 뽑으려면

1. 동전은 최대한 사용하지 말고 공짜로 받은 내 패에서 해결 후 다음 라운드로 가는게 좋다.

2. 동전을 사용한다하면, 최대한 적게 사용해야 한다. 내 패 안에 있는 카드와 조합할 수 있는 하나의 카드를 코인을 주고 사용하자.

3. 무조건 사용해야 한다. 두개를 사용하더라도 가져오자.

이 순서로 그리디 방법을 생각해야했다.

난 뽑은 카드를 버린다 생각했는데 이걸 다른 장소에 저장하고 코인을 사용하며 재사용 할 생각은 전혀 몰랐다.

생각을 많이 해야하는 문제지만 그래도 재밌었다.

#include <string>
#include <vector>
#include <bits/stdc++.h> 
using namespace std;

int N; 

bool check(map<int,int>& cardsMap, map<int,int>& drawMap){
    for(auto& it : cardsMap){
        int match = N - it.first; 
        
        if(drawMap.count(match)){
            cardsMap.erase(it.first); 
            drawMap.erase(match); 
            
            return true; 
        }
    }
    
    return false; 
}

int solution(int coin, vector<int> cards) {
    int round = 1;
    map<int,int> cardMap, drawMap; 
    N = cards.size() + 1; 
    for(int i =  0; i < cards.size() / 3; i++){
        cardMap[cards[i]]++; 
    }
    
    int index = cards.size() / 3; 
    
    while(index < cards.size()){
        
        drawMap[cards[index]]++; 
        drawMap[cards[index+1]]++; 
        
        if(cardMap.size() >= 2 && check(cardMap,cardMap)){
            round++; 
        }
        else if(cardMap.size() >= 1 && coin >= 1 && check(cardMap, drawMap)){
            round++;
            coin--; 
        }
        else if(coin >= 2 && check(drawMap, drawMap)){
            round++;
            coin-=2; 
        }
        
        else{
            break; 
        }
        
        
        index += 2; 
        
    }
    
    
    
    return round;
}