양궁대회

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

완전 탐색 문제 + DFS

시간이 10초 이내인 것을 보면 완전 탐색 문제인 것을 알 수 있다.
index=0부터가 10점이라, 점수와 index를 헷갈릴 수 있었다.

푸는데 약 2시간 반 정도의 시간이 걸렸다.

정답 기준

1. 점수차가 가장 크고
2. 더 작은 점수를 맞춘 경우
3. 작은 점수를 많이 맞춘 경우

라서 완전 탐색으로 모든 답을 구한 후
위 세가지 방법으로 정렬해야 했다.

쉽게 생각해 10점->9점...으로 채워나가는 방법도 있지만
2번의 조건을 고려해 정렬 과정을 생략하기 위해
index가 큰 값부터, 0점->1점-> ...으로 채워나가지는 Tree를 그렸다.

그리고 이 Tree를 DFS로 탐색할 경우 2, 3을 만족하게 된다.

그 다음에는 점수차 MAX값을 갱신할 때 마다 답을 교체해주면 된다.

어려웠던 점은 라이언이 더 많이 맞춘 경우에

라이언의 점수는 lion+=10-index
어피치의 점수는 apeach-=10-index

를 고려하여야 하는 점이다.

import java.util.*;
class Solution {
    static ArrayList<boolean []> result;
    static int depth;
    static int max=0;
    static boolean flag=false;
    static boolean[] ans = new boolean[11];
    public int[] solution(int n, int[] info) {
        int[] answer = new int[info.length];
        depth=n;
        //해당 depth에서 점수를 가져가려면 info+1만큼 화살을 맞추면 된다.
        //depth에서 점수를 얻는 경우/얻지 못하는 경우로 나눈다.
        //가능성 트리를 그려야함.
        result = new ArrayList<>();
        boolean [] visit = new boolean[info.length]; 
        int apeach=0;
        int lion=0;
        //현재 어피치의 점수
        for(int i=0; i<info.length; i++){
            if(info[i]!=0){
                apeach += (10-i);
            }
        }
        dfs(depth, visit, lion, n, info, apeach); //뒤에서부터 앞으로 채워나간다.
        int remain = n;
        for(int i=0; i<info.length; i++){
                System.out.print(ans[i]+" ");
                 if(ans[i]){
                        answer[i]=info[i]+1;
                        remain -= info[i]+1;
                    }else answer[i]=0;
        }
        if(remain!=0){
            answer[info.length-1]=remain; //화살이 남은 경우 0을 맞췄다고 가정한다.
        }
        if(!flag){ //답을 발견하지 못한 경우
            return new int[]{-1};
        }
       
        return answer;
    }
    public void dfs(int d, boolean[] visit, int lion, int remain, int[] info, int apeach){   
        
        if(remain<0){ //더이상 화살이 없음-> 검사X
            return;
        }
        if(d<0){ //0->10까지 검사 완료
            if(lion>apeach) {
                    if(max<(lion-apeach)){
                        max = lion-apeach;
                        for(int i=0; i<info.length; i++){
                            ans[i]=visit[i];
                        } // 현재 상태 값을 저장해준다. 
                        
                        flag=true;
                    }
                }
               // System.out.print("sum :"+sum+" score: "+score);
            return;
        }
        
        //현재 과녁에 쏠 수 있는 경우
        // 어피치가 쏘지 않은 과녁일떄/쏜 과녁일 떄에 따라 필요 화살수가 달라진다.
        visit[d]=true;
        if(info[d]==0) dfs(d-1, visit, lion+(10-d), remain-1, info, apeach);
        else dfs(d-1, visit, lion+(10-d), remain-(info[d]+1), info, apeach-(10-d));
        
        //현재 과녁에 쏘지 않는 경우
        visit[d]=false;
        //System.out.print("reamin "+remain);
        dfs(d-1, visit, lion, remain, info, apeach);
    }

}