프로그래머스 양궁대회 (JAVA)

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

프로그래머스

 

저는 dfs를 통해 문젤르 해결하였습니다.

라이언이 해당 depth(점수)에 몇개를 넣을 지를 결정하였고, 라이언이 가장 큰 점수 차이로 우승할 수 있는 방법이 여러개라면, 가장 낮은 점수를 많이 맞친 경우를 return 해야하기 때문에 저는 남은 화살은 전부 0에 넣도록 구현하였습니다.

그리고 결과값의 초기화는 같은 점수 차라면 배열의 뒤 (점수가 낮은 부분) 부터 개수를 비교하여 더 큰쪽으로 초기화 시켜 문제를 해결하였습니다. 

 

import java.util.*;

class Solution {
    private static final int[] NOT_FOUND = {-1};
    private static final int SIZE = 11;
    private static int[] answer = NOT_FOUND;
    private static int answerGap = 0;
    public int[] solution(int n, int[] info) {
        int[] score = new int[SIZE];
        dfs(0,n,info,score);
        return answer;
    }
    private static void dfs(int depth, int n, int[] info, int[] score){
        if(depth == SIZE){
            int gap = 0;
            if(n > 0){
                score[SIZE-1] += n;
            }
            for(int i = 0 ; i < SIZE ; i++){
                if(info[i] < score[i]){
                    gap += 10 - i;
                }else if(info[i] != 0){
                    gap -= 10 - i;
                }
            }
            if(gap == answerGap && gap != 0){
                for(int i = SIZE - 1 ; i >= 0 ; i--){
                    if(answer[i] < score[i]){
                        answer = Arrays.copyOf(score,SIZE);
                        break;
                    }else if(answer[i] > score[i]){
                        break;
                    }
                }
            }
            if(gap > answerGap){
                answerGap = gap;
                answer = Arrays.copyOf(score,SIZE);
            }
            if(n > 0){
                score[SIZE-1] -= n;
            }
            return ;
        }   
        if(n > info[depth]){
            score[depth] = info[depth] + 1;
            dfs(depth+1,n - info[depth] - 1,info,score);
            score[depth] = 0;
        }
        dfs(depth+1,n,info,score);
        return ;
    }
}