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



문제는 이거고 코드 보여달란 요청이 있어서 올려봄

그리디 문제인데 내가 재귀로 풀어본게 신기했나봄




import java.util.*;

class Solution {
static int N;
static int answer;
static int nextSum;

public int solution(int coin, int[] cards) {
N = cards.length;
int startN = N / 3;
Set<Integer> hand = new HashSet<>();
for (int i = 0; i < startN; i++) {
hand.add(cards[i]);
}
nextSum = N + 1;
answer = 0;
solve(hand, startN, coin, cards, 0);
return answer;
}

public static void solve(Set<Integer> hand, int cur, int coin, int[] cards, int round) {
round++;

if (cur + 1 < N) {
int card1 = cards[cur];
int card2 = cards[cur + 1];

boolean progressed = false;

progressed |= tryPair(hand, cur + 2, coin, cards, round);

if (coin >= 1) {
hand.add(card1);
progressed |= tryPair(hand, cur + 2, coin - 1, cards, round);
hand.remove(card1);
}

if (coin >= 1) {
hand.add(card2);
progressed |= tryPair(hand, cur + 2, coin - 1, cards, round);
hand.remove(card2);
}

if (coin >= 2) {
hand.add(card1);
hand.add(card2);
progressed |= tryPair(hand, cur + 2, coin - 2, cards, round);
hand.remove(card1);
hand.remove(card2);
}

if (!progressed) {
answer = Math.max(answer, round);
}
} else {
boolean progressed = tryPair(hand, cur, coin, cards, round);
if (!progressed) {
answer = Math.max(answer, round);
}
}
}

public static boolean tryPair(Set<Integer> hand, int cur, int coin, int[] cards, int round) {
boolean found = false;

//O(1) 룩업
for (int card : new ArrayList<>(hand)) {
int pair = nextSum - card;
if (pair != card && hand.contains(pair)) {
found = true;
hand.remove(card);
hand.remove(pair);
solve(hand, cur, coin, cards, round);
hand.add(card);
hand.add(pair);
}
}

return found;
}
}



이게 내가 푼 코드임


틀린답이니까 돌려도 시간초과 날거임


아래는 고닉 노력이가 탑다운 dp로 안풀리나 궁금해 하길래

내가 먼저 ai 돌려서 실험해봤음 ㅋㅋ

그리디가 아니여도 풀리더라


내가 좀 더 잘 풀었으면 풀 수 있었을텐데 아쉽


import java.util.*;

class Solution {
static Map<String, Integer> memo;

public int solution(int coin, int[] cards) {
int n = cards.length;
int target = n + 1;

boolean[] mycards = new boolean[n];
for (int i = 0; i < n / 3; i++) {
mycards[cards[i] - 1] = true;
}

// 초기 손패끼리 페어 수
int life = 0;
for (int i = 0; i < n / 2; i++) {
if (mycards[i] && mycards[n - i - 1]) life++;
}

// 각 라운드에서 뽑는 카드로 생기는 페어 정보를 미리 계산
// gainLife[i]: i라운드에서 뽑은 카드 중 손패와 짝이 되는 수 (코인1짜리)
// gainTemp[i]: i라운드에서 뽑은 카드끼리 or 이전 뽑은 카드와 짝이 되는 수 (코인2짜리)
int rounds = n / 3;
int[] gainLife = new int[rounds + 1];
int[] gainTemp = new int[rounds + 1];
boolean[] newcards = new boolean[n];

for (int i = 1; i <= rounds; i++) {
int card1 = cards[n / 3 + 2 * (i - 1)];
int card2 = cards[n / 3 + 2 * (i - 1) + 1];

if (mycards[n - card1]) gainLife[i]++;
if (mycards[n - card2]) gainLife[i]++;

if (newcards[n - card1]) gainTemp[i]++;
else newcards[card1 - 1] = true;

if (newcards[n - card2]) gainTemp[i]++;
else newcards[card2 - 1] = true;
}

// 탑다운 DP: dp(라운드, 코인, life, templife) → 최대 도달 라운드
memo = new HashMap<>();
return dp(1, coin, life, 0, gainLife, gainTemp, rounds);
}

// 현재 라운드에서 최대 몇 라운드까지 갈 수 있는지
static int dp(int round, int coin, int life, int templife,
int[] gainLife, int[] gainTemp, int maxRound) {

if (round > maxRound) return round;

String key = round + "," + coin + "," + life + "," + templife;
if (memo.containsKey(key)) return memo.get(key);

// 이번 라운드에서 뽑은 카드 반영
int newLife = life;
int newTemp = templife;

// 뽑은 카드 중 손패와 짝 → 코인 1개씩 써서 life로 전환 가능
// 선택: 0 ~ gainLife[round]개를 코인 써서 가져감
int maxGain = Math.min(gainLife[round], coin);
newTemp += gainTemp[round];

int best = round; // 이번 라운드에서 끝나는 경우

// 손패 짝을 몇 개 코인으로 가져갈지 선택
for (int take = 0; take <= maxGain; take++) {
int curLife = newLife + take;
int curCoin = coin - take;
int curTemp = newTemp;

// templife를 코인2로 전환할지 선택
int maxTemp = Math.min(curTemp, curCoin / 2);
for (int t = 0; t <= maxTemp; t++) {
int finalLife = curLife + t;
int finalCoin = curCoin - 2 * t;
int finalTemp = curTemp - t;

if (finalLife <= 0) continue;

// life 1개 소모하고 다음 라운드
best = Math.max(best,
dp(round + 1, finalCoin, finalLife - 1, finalTemp,
gainLife, gainTemp, maxRound));
}
}

memo.put(key, best);
return best;
}
}