양국대회 [자바]

 

🧫 문제 분석

✔️ 출처

양국대회 level 2

📖 문제

 

최대 점수이면서 가장 낮은 점수를 가장 많이 맞춘 스코어 배열을 만들어야하는 문제

 

 

최대 점수를 만들되 어피치가 가진 점수를 빼앗기 위해서는

어피치가 맞춘 화살 개수보다 더 많이 맞춰야 해당 점수를 획득할 수 있다. 

 

라이언이 각 점수를 화살로 맞추는 경우와 맞추지 않는 경우 2가지를 dfs로 탐색하여 풀었다.

(최대 점수가 10점이기에 시간복잡도는 길어야 O(2^11)이다)

 

그리고 최대 점수를 갱신하고, 해당 점수를 얻은 화살 맞춘 스코어 배열을 list에 저장하면서 진행한다. 

같은 점수라도 다 저장한다.

 

탐색이 끝나면 정답 후보를 탐색한다. 같은 점수인 정답 후보 중 가장 낮은 점수를 더 많이 획득한 경우를 구한다.

 

구한 정답 후보에서 안쏜 화살 개수를 구하는데 그 이유는 위에서 진행한 dfs 탐색에서 모든 화살을 사용하지 않은 경우가 있기 떄문이다.

안 쏜 화살 개수만큼 최하점에 화살개수를 모두 더해준다.

 

또한 정답 후보를 통해 어피치의 점수와 라이언의 점수를 구하여 비교한다. 만약 어피치 점수 >= 라이언 점수라면 정답이 없으므로 -1을 반환한다. 

 

 

 

 

 

 

---

🔅 문제 풀이

import java.util.*;

class Solution {
    // a = b일 경우는 어피치가 k점
    // k 점을 여러발 맞춰도 k점만 가져감
    //  최종 점수가 같을 경우 어피치를 우승
    //라이언이 가장 큰 점수 차이로 우승이 목표 
    
    static int apeach = 0;
    static int[] arr = new int[11];
    static List<int[]> list = new ArrayList<>();
    static int max = 0;
    
    public int[] solution(int n, int[] info) {
        
        // 어피치의 총 점수 합을 구함
        for (int i = 0; i < 11; i++) {
            apeach += info[i];
        }
        
        // 최대값으로 이기는 모든 경우를 탐색 
        dfs(info, 0, 0, n);
        
        // 같은 점수가 여러개인 경우 가장 낮은 점수를 더 많이 맞힌 경우를 구함 
        int[] answer = list.get(0); 
        for (int i = 1; i < list.size(); i++) {
            int[] tmp = list.get(i);
            for (int j = 10; j >= 0; j--) {
                
                if (answer[j] < tmp[j]) {
                    answer = tmp;
                    break;
                } else if (answer[j] > tmp[j]){
                    break;
                }
            }
        }
        
        // 총 화살의 개수를 세어 안쏜 화살을 구함
        // 정답 후보의 어피치 총합과 라이언 총합을 구해서 어피치 >= 라이언 일 경우 답이 없으므로 -1 리턴 
        int cnt = 0;
        int sum = 0, apeachSum = 0;
        for (int i = 0; i < answer.length; i++) {
            cnt += answer[i];
            if (answer[i] > info[i]) {
                sum += 10 - i;
            } else {
                apeachSum += info[i] > 0 ? 10 - i : 0;
            }
        }
        
        if (sum <= apeachSum) return new int[] {-1};
        // 가장 낮은 점수에 모두 더함
        if (cnt < n) answer[10] += n - cnt;
        
        return answer;
        // 라이언이 가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지 일 경우, 가장 낮은 점수를 더 많이 맞힌 경우
        //  라이언이 우승할 수 없는 경우(무조건 지거나 비기는 경우)는 [-1]을 return 
    }
    
    private void dfs(int[] info, int idx, int score, int arrow) {
        
        if (idx == 11) {
            return;
        }
        
        if (apeach < score) {
            if (max < score - apeach) {
                max = score - apeach;
                
                list.clear();
                list.add(arr.clone());
            } else if (max == score - apeach) {
                list.add(arr.clone());
            }
        }
        
        
        // idx 번째 수를 얻는 경우 
        if (info[idx] + 1 <= arrow) {
            
            if (info[idx] > 0) {
                apeach -= (10 - idx);
            }
            
            arr[idx] = info[idx] + 1;
            dfs(info, idx + 1, score + (10 - idx), arrow - info[idx] - 1);
            arr[idx] = 0;
            
            if (info[idx] > 0) {
                apeach += (10 - idx);
            }
        }
        
        // 얻지 않는 경우 
        dfs(info, idx + 1, score, arrow);
        
    }
}

 

 

🔅 리팩토링

❗ 오답노트 / 필요한 지식