[Algorithm] 프로그래머스 - n + 1 카드게임

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

접근

그리디 알고리즘 문제다.

이 문제는 작정하면 정말 까다로워질 수 있는 문제다.

그래도, 문제에서 제한을 많이 주었기 때문에 그런 상황은 피할 수 있었다.

cards 의 원소가 중복되지 않고 n 과 cards 의 길이가 같기 때문에 coin 의 비용이 가장 적게 드는 경우를 우선 선택하면 된다.

가장 적게 드는 비용은 동전 1개이고, $\frac{n}{3}$ 번 이하의 카드를 포함하는 조합에서만 가능하다.

하지만 비용이 크다고 해서 선택하지 않고 다음 라운드로 넘어가면 정작 필요할 때 그 카드를 사용하지 못할 수 있다.

그래서 각 라운드마다 제출하는 카드를 고정시키지 않고 이전 라운드의 카드를 선택하거나 변경시킬 수 있어야 한다.

비용이 얼마나 들든 살 수 있는 만큼 현재 라운드에서 카드를 산다. 이후 라운드에서 그 카드를 교환하면 되기 때문이다.

하지만, 비용이 동전 2개임에도 교환 가능한 카드와 교환 불가능한 카드가 존재한다.

교환 불가능한 카드는 이미 그 카드를 라운드를 거치며 제출한 경우다. 이 경우에는 카드가 나의 소유를 벗어났으므로 교환할 수 없다.

이 경우만 구분하면 코인이 없을 때 비용이 더 적게 드는 쪽으로 상황을 바꿀 수 있다.

소스코드(Java)

class Solution {

    public int solution(int coin, int[] cards) {

        int nLife = 0; //동전 0 혹은 1개 비용에 해당하는 목숨
        int dLife = 0; //동전 2개 비용에 해당하는 목숨
        int round = 0;
        int cnt = 0; //동전 2개 비용에 해당하는 교환 가능 횟수
        int ni = cards.length/3;

        for(int i = 0; i < ni-1; i++) {
            for(int j = i+1; j < ni; j++) {
                if(cards[i]+cards[j] == cards.length + 1) {
                    nLife += 1;
                }
            }
        }

        while(nLife + dLife >= 0 && ++round <= ni) {

            int prevCnt = cnt;

            for(int j = 0; j < 2; j++) {
                for(int i = 0; i < 2 * (round-1) + ni + j; i++) {
                    int newCard = cards[ni+2*(round-1)+j];
                    if(i < ni) {
                        if(newCard + cards[i] == cards.length+1) {
                            if(cnt - 1 >= 0 && coin == 0) {
                                cnt -= 1;
                                dLife -= 1;
                                coin += 2;
                            }

                            if(coin - 1 >= 0) {
                                nLife += 1;
                                coin -= 1;
                            }
                        }
                    } else {
                        if(newCard + cards[i] == cards.length+1) {
                            if(coin-2 >= 0) {
                                dLife += 1;
                                coin -= 2;
                                cnt += 1;
                            }
                        }
                    }
                }
            }

            //동전 2개 비용에 해당하는 카드 조합만 제출 가능하다면, 해당 구매는 이후 교환 불가
            if((nLife + dLife) == 1 && cnt - prevCnt == 1) {
                cnt -= 1;
            }

            //교환 가능한 구매의 카드 조합을 제출해야 한다면, 해당 구매는 이후 교환 불가
            if(nLife == 0 && cnt > 0) {
                dLife -= 1;
                cnt -= 1;
            } else {
                nLife -= 1;
            }
        }
        return round;
    }
}