[프로그래머스][Level.2] 양궁대회

문제 풀이📝

---

완전 탐색(조합)을 이용한 풀이

1. 라이언이 득점할 수 있는 모든 점수들의 조합을 구한다.

2. 해당 조합이 유효한지 체크한다.

• 화살을 초과해서 사용하지 않는지?
• 라이언이 이기는 경우인지?
• 가장 큰 점수 차이인지?
• 기존 점수 차이와 같을 경우, 더 낮은 점수를 많이 맞추는지?

3. 만약 유효하다면 기존의 case를 해당 case로 갱신한다.

 

구현🛠️

---

class Solution {
    
    private final int MAX = 11;
    private int N;
    private int[] apeach;
    private boolean[] choice;
    
    private int maxGap;
    private int[] lion;
    
    public int[] solution(int n, int[] info) {
        
        this.N = n;
        this.apeach = info;
        this.choice = new boolean[MAX];
        
        this.maxGap = 0;
        this.lion = new int[MAX];
        
        
        for (int i = 1; i <= N; i++) {
            dfs(0, 0, i);
        }
        
        if (maxGap == 0) {
            return new int[]{-1};
        }
        
        return lion;
    }
    
    public void dfs(int start, int cnt, int limit) {
        if (cnt == limit) {
            int arrows = N;
            int apeachScore = 0;
            int lionScore = 0;
            int[] cur = new int[MAX];
            
            for (int i = 0; i < MAX; i++) {
                if (choice[i]) {
                    arrows = arrows - (apeach[i] + 1);
                    lionScore = lionScore + (10 - i);
                    cur[i] = apeach[i] + 1;
                    continue;
                }
                cur[i] = 0;
                if (apeach[i] != 0) {
                    apeachScore = apeachScore + (10 - i);
                }                
            }
            
            // 화살을 다 써버리는 경우
            if (arrows < 0) {
                return;
            }
            // 화살이 남아있는 경우
            if (arrows > 0) {
                // 가장 낮은 점수를 더 쏜다.
                cur[10] = cur[10] + arrows;
            }
            
            int curGap = lionScore - apeachScore;
            
            // 라이언이 진 경우
            if (curGap < 0) {
                return;
            }
            
            // 가장 큰 점수 차이가 아닌 경우
            if (curGap < maxGap) {
                return;
            }
            
            // 기존의 점수 차이보다 더 큰 점수 차이인 경우
            if (curGap > maxGap) {
                maxGap = curGap;
                lion = cur;
            }
            
            // 기존의 점수 차이와 같은 경우 -> 더 낮은 점수를 많이 맞힌 경우를 pick
            if (curGap == maxGap) { 
                for (int i = MAX - 1; i >= 0; i--) {
                    // 현재가 더 낮은 점수를 많이 맞힌 경우
                    if (cur[i] > lion[i]) {
                        maxGap = curGap;
                        lion = cur;
                        return;
                    }
                    // 기존이 더 낮은 점수를 많이 맞힌 경우
                    if (cur[i] < lion[i]) {
                        return; // 아무것도 갱신하지 않는다
                    }
                }
            }
        }
        
        for (int i = start; i < MAX; i++) {
            choice[i] = true;
            dfs(i + 1, cnt + 1, limit);
            choice[i] = false;
        }
    }
}

 

실행결과✅

---

테스트 1 〉	통과 (0.27ms, 79.2MB)
테스트 2 〉	통과 (0.89ms, 76.2MB)
테스트 3 〉	통과 (1.16ms, 79.4MB)
테스트 4 〉	통과 (0.87ms, 75.5MB)
테스트 5 〉	통과 (1.19ms, 68.9MB)
테스트 6 〉	통과 (1.24ms, 78.5MB)
테스트 7 〉	통과 (1.02ms, 79.7MB)
테스트 8 〉	통과 (0.30ms, 72.7MB)
테스트 9 〉	통과 (1.03ms, 76.4MB)
테스트 10 〉	통과 (0.20ms, 77.2MB)
테스트 11 〉	통과 (0.49ms, 78.5MB)
테스트 12 〉	통과 (0.73ms, 78.3MB)
테스트 13 〉	통과 (0.72ms, 77.7MB)
테스트 14 〉	통과 (1.08ms, 79.8MB)
테스트 15 〉	통과 (1.12ms, 75.5MB)
테스트 16 〉	통과 (1.04ms, 78.6MB)
테스트 17 〉	통과 (0.69ms, 78.8MB)
테스트 18 〉	통과 (0.14ms, 76.5MB)
테스트 19 〉	통과 (0.03ms, 73.5MB)
테스트 20 〉	통과 (0.80ms, 80.4MB)
테스트 21 〉	통과 (1.13ms, 76.4MB)
테스트 22 〉	통과 (0.90ms, 74.1MB)
테스트 23 〉	통과 (0.16ms, 71.7MB)
테스트 24 〉	통과 (1.03ms, 75.6MB)
테스트 25 〉	통과 (1.04ms, 78.2MB)