PGMS_92342_양궁대회

깊이 우선 탐색(DFS)로 화살 개수를 조합해서 푸는 문제

동점이라면 낮은 화살 개수가 많은 걸 정답으로 친다
그러면 무조건 0 많은 게 정답이기 때문에 조합 문제긴 한데 화살 주는 로직이 있다

1. 1~10점 사이면 어피치 + 1개로 최소 개수만 맞춰서 주거나/안 주거나
2. 남는 화살 0점에 전부 다 쏜다
   이렇게 나눠진다

삽질

1시간 삽질하면서 테스트 케이스만 20개 만들었는데 다 통과돼서 더 의문이었다
그런데 당연함. 테케를 score가 최대일 때 맞게 했으니까 당연히 통과함 ㅎㅎ
최대 점수가 아니라 복숭아랑 라이언이랑 점수 차이 제일 클 때를 구하는 거였다...

import java.util.*;

class Solution {    
    static int N;
    static int[] apeach;
    static int[] answerArrows = new int[] {-1};
    static int answerScore = 0;
    
    public int[] solution(int n, int[] info) {
        // 라이언이 불쌍한 문제
        N = n;
        apeach = info;
        dfs(0, 0, new int [11]);
        return answerArrows;
    }
    
    static int checkScore(int[] arrows) {
        int apeachScore = 0;
        int lionScore = 0;
        
        for(int i = 0; i < 10; i ++) {
            if(apeach[i] < arrows[i]) {
                lionScore += 10 - i;
            } else {
                if(apeach[i] > 0) {
                    apeachScore += 10 - i;
                }
            }
        }
        
        // 점수 차가 최대
        return lionScore <= apeachScore ? -1 : lionScore - apeachScore;
    }
    
    static void dfs(int start, int cnt, int[] arrows) {
        if(cnt == N) {
            int score = checkScore(arrows);
            
            if(score == -1) {
                return;
            }
            
            if(answerScore == score) {
                for(int i = 10; i >= 0; i --) {
                    if(answerArrows[i] < arrows[i]) {
                        answerArrows = arrows;
                        answerScore = score;
                        break;
                    } else if(answerArrows[i] > arrows[i]) {
                        break;
                    }
                }
            }
            
            else if(answerScore < score) {
                answerArrows = arrows;
                answerScore = score;
            }
            
            return;
        }
        
        for(int i = start; i < 11; i ++) {
            if(i < 10 && cnt + apeach[i] + 1 <= N) {
                arrows[i] = apeach[i] + 1;
                dfs(i + 1, cnt + apeach[i] + 1, Arrays.copyOf(arrows, 11));
                arrows[i] = 0;
            }

            else if(i == 10) {
                arrows[i] = N - cnt;
                dfs(i + 1, N, Arrays.copyOf(arrows, 11));
                arrows[i] = 0;
            }
        }
    }
}