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

풀이	반례	2시간
o	o	x

성공한 풀이

어떤 카드 조합이든 상관없다.
중요한 건 코인을 적게 쓰고 다음 라운드로 넘어가는 것.
미리 선택하지 않고 필요할 때 이제까지 거쳐온 카드들 중 고른다.
우선순위는 원조 카드들 조합 > 한 개만 새로 사면 되는 조합 > 두 개 다 새로 사야하는 조합.

import java.util.*;

class Solution {
    
    static int n, answer, zero;
    
    static Set<Integer> origin, newCards;
    
    public boolean choice(int c) {
        int f = n+1-c;
        if (newCards.contains(f)) {
            newCards.remove(f);
            return true;
        }
        return false;
    }
    
    public int solution(int coin, int[] cards) { 
        
        n = cards.length;
        origin = new HashSet<>();
        newCards = new HashSet<>();
        for (int i = 0; i < n/3; i++) {
            origin.add(cards[i]);
        }
        
        for (int i = 0; i < n/3; i++) {
            int c = cards[i];
            int f = n+1-c;
            if (origin.contains(f)) {
                zero++;
                origin.remove(c);
                origin.remove(f);
            }
        } 
        
        boolean payable = true;
        Label : for (int round = 1; round <= n/3+1 && payable; round++) {
            int idx = n/3 + (round-1)*2;
            payable = false;
        
            answer = Math.max(round, answer);
            if (idx >= n) break;
            
            newCards.add(cards[idx]);
            newCards.add(cards[idx+1]);

            if (zero > 0) {
                zero--;
                payable = true;
                continue;
            } else if (coin > 0) {
                for (int c : origin) {
                    if (choice(c)) {
                        coin--;
                        origin.remove(c);
                        payable = true;
                        continue Label;
                    }
                }
                if (coin < 2) break;
                for (int c : newCards) {
                    if (choice(c)) {
                        coin-=2;
                        newCards.remove(c);
                        payable = true;
                        break;
                    }
                }
            }
        }
        
        return answer;
    }
}

실패한 풀이 (16/20)

zero = 초기 카드 중에서 만들 수 있는 조합
one = 초기 카드 하나, 사야하는 카드 하나로 만들 수 있는 조합
two = 사야하는 카드 두개로 만들 수 있는 조합

prob = 해당 라운드에서 만들 수 있는 최대 조합의 수(coin 고려)

해당 라운드에서 최선을 다한 조합 수가 round 숫자보다 크면 된다! 라는 논리로 짠 코드다.

coin 2개인 경우,
1라운드에서 two 조합으로 해당 라운드의 2개를 사야만 1개 페어를 내고 통과할 수 있었는데
2라운드에서 해당 라운드의 2개를 사서 one 조합으로 2개 페어를 내고 통과할 수 있는 경우가 반례로 존재했다.
테스트케이스에 이걸 넣어보세요. 2, [1,2,3,4,5,6], 2
결과가 3으로 나온답니다.

이 논리는 모든 라운드를 독립 시행으로 보기 때문에 틀린 것이다.
근데 어떻게 또 80점씩이나 나왔다..?

이 반례를 떠올리지 못해서 왜 안 되는지 납득을 못하고 prob 조건이 잘못되었나... 쳐다보며 시간을 많이 낭비했다.

import java.util.*;

class Solution {
    
    static int n, answer, zero, one, two;
    
    static boolean[] selection;
    static Set<Integer> origin;
    
    public void choice(int c) {
        int f = n+1-c;
        if (selection[f]) {
            if (origin.contains(f)) one++;
            else two++;
        }
    }
    
    public void back(int round, int coin, int[] cards) {
        int idx = n/3 + (round-1)*2;
        
        answer = Math.max(round, answer);
        if (idx >= n) return;
        
        selection[cards[idx]] = true;
        choice(cards[idx]);
        selection[cards[idx+1]] = true;
        choice(cards[idx+1]);
        
        int prob = zero + Math.min(one, coin) + Math.min(Math.max(0, coin-one), two*2)/2;
        
        if (prob >= round) {
            back(round+1, coin, cards);
        }
    }
    
    public int solution(int coin, int[] cards) { 
        
        n = cards.length;
        selection = new boolean[n+1];
        origin = new HashSet<>();
        for (int i = 0; i < n/3; i++) {
            selection[cards[i]] = true;
            origin.add(cards[i]);
        }
        
        for (int i = 0; i < n/3; i++) {
            int c = cards[i];
            int f = n+1-c;
            if (selection[f]) zero++;
        } 
        zero/=2;
        
        back(1, coin, cards);
        
        return answer;
    }
}