[2024 KAKAO WINTER INTERNSHIP] n+1 카드게임 (C++)

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

프로그래머스

풀이

매 라운드마다 할 수 있는 선택지는 다음과 같다.

1) 뽑은 두 장의 카드를 모두 버린다.

2) 뽑은 두 장의 카드 중 한 장의 카드(a)만 가져온다.

3) 2에서 가져온 카드 a 외의 다른 한 장의 카드(b)만 가져온다.

4) 두 장의 카드(a, b) 모두 가져온다.

 

위 선택지를 모두 계산해가며 모든 경우의 수를 계산하면 시간 초과가 발생한다.

이보다 더 효율적으로 생각하여 문제를 접근해보자.

 

카드를 버린다고 생각하지 말고, 선택한다 생각하자.

이 문제는 "매 턴 원하는 카드를 코인을 지불하고 가져올 수 있다"라고 해석할 수 있다.

예제 1번의 경우를 생각해보자. 기본으로 주어지는 카드는 3, 6, 7, 2이다.

1라운드) 1, 10을 추가한 3, 6, 7, 2, 1, 10 중 6과 7을 버린다. 이 때 코인을 소모하지 않는다. (두 장 모두 처음에 뽑았으므로)

2라운드) 5, 9를 추가한 3, 2, 1, 10, 5, 9 중 3과 10을 버린다. 이 때 코인 1개를 소모한다. (3은 처음에 뽑았고 10은 나중에 선택)

3라운드) 8, 12를 추가한 2, 1, 5, 9, 8, 12 중 5와 8을 버린다. 이 때 코인 2개를 소모한다. (두 장 모두 나중에 뽑았으므로)

...

 

따라서 위 문제는 아래와 같은 우선순위를 지켜가며 버릴 카드를 선택하면 풀 수 있다.

우선순위 1) 코인 0개를 필요로 하는 카드 2장을 버린다. (두 장 모두 처음에 뽑은 카드)

우선순위 2) 코인 1개를 필요로 하는 카드 2장을 버린다. (한 장은 처음에 뽑은 카드, 한 장은 나중에 뽑은 카드)

우선순위 3) 코인 2개를 필요로 하는 카드 2장을 버린다. (두 장 모두 나중에 뽑은 카드)

 

코드

#include <string>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int able[1000];

int solution(int coin, vector<int> cards) {    
    int n = cards.size();
    priority_queue<int, vector<int>, greater<int>> pq;
    
    for (int i = 0; i < n/3; i++){
        int cur = cards[i];
        able[cur] = 1;
        if (able[n+1-cur]){
            pq.push(0);
        }
    }
    
    int round = 1;
    while (true){
        // 뽑을 카드가 없다면 종료
        if (round == n/3+1){
            break;
        }
        
        int idx = n/3 + (round-1)*2;
        int target1 = cards[idx];
        int target2 = cards[idx+1];
        
        able[target1] = 2;
        able[target2] = 2;
        
        if (able[n+1-target1]){
            pq.push(able[n+1-target1]);
        }
        if (able[n+1-target2]){
            pq.push(able[n+1-target2]);
        }
                
        // 버릴 카드가 없다면 종료
        if (pq.empty() || coin < pq.top()){
            break;
        }
        
        // 카드 버리기
        coin -= pq.top();
        pq.pop();
        
        round++;
    }
    
    return round;
}