[2022 KAKAO BLIND RECRUITMENT] 양궁대회

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/92342

이 문제는 백트래킹을 이용해서 풀 수 있습니다. 문제에서 반복을 진행하는 배열의 크기가 11이기 때문에 모든 조건을 하나씩 탐색해도 시간 초과가 발생하지 않습니다. 따라서 조건에 맞게 값을 하나씩 변경해가면서 최종 결과값과 비교를 통해 값을 구하면 되겠습니다.

다음은 코드입니다.

import java.util.*;

class Solution {
    static int[] ryan = new int[11];
    static int diff = -1;
    static int[] answer = new int[11];
    
    static void backtracking(int N, int[] apeach, int cnt, int idx){
        if(cnt == N){
            int asum = 0;
            int rsum = 0;
            
            for(int i=0;i<=10;i++){
                if(apeach[i]==0 && ryan[i]==0) continue;
                
                if(apeach[i] < ryan[i]) rsum += 10-i;
                else asum += 10-i;
            }
            
            if(asum < rsum){
                if(diff < (rsum-asum)){
                    diff = rsum-asum;
                    answer = ryan.clone();
                }
                else if(diff == (rsum-asum)){
                    for(int i=10;i>=0;i--){
                        if(answer[i] < ryan[i]){
                            answer = ryan.clone();
                            break;
                        }
                        else if(answer[i] > ryan[i]) break;
                    }
                }
            }
            
            return;
        }
        
        for(int i=idx;i>=0;i--){
            if(ryan[i] > apeach[i]) continue;
            
            ryan[i]++;
            backtracking(N,apeach,cnt+1,i);
            ryan[i]--;
        }
        
    }
    
    public int[] solution(int n, int[] info) {
        backtracking(n,info,0,10);
        
        boolean isEmpty = true;
        for(int i=0;i<=10;i++){
            if(answer[i]!=0){
                isEmpty = false;
                break;
            }
        }
        if(isEmpty) return new int[] {-1};
        else return answer;
    }
}