양궁대회

풀이
DFS를 사용하지만 모든 트리를 확인하는것이 아닌 가능한 경우만 탐색한다.
가장 마지막경우 남은화살을 모두 사용하는것으로 간주.

모든 트리를 확인할 필요가 없다는것이 이 문제의 주요관점인것같다.

코드

class Solution {
    int maxDepth;//최고깊이
    int[] aInfo; //어피치 info
    int[] lInfo; //라이언 info
    int maxValue =0; //점수차이
    public int[] solution(int n, int[] info) {
        maxDepth =n;
        aInfo = info;
        dfs(0,new int[11],0);
        System.out.println(maxValue);
        return maxValue==0?new int[]{-1} :lInfo;
    }
    int infoValueDiff(int[] Info){
        int aValue=0,lValue=0;
        for(int i=0;i<11;i++){
            if(Info[i]>aInfo[i]){
                lValue+=10-i;
            }else if(aInfo[i]!=0){
                aValue+=10-i;
            }
        }
        return lValue-aValue;
    }
    boolean infoDiff(int[] Info){
        for(int i=10;i>=0;i--){
            if(lInfo[i]<Info[i]){
                return true;
            }else if(lInfo[i]>Info[i]){
                return false;
            }
        }
        return false;
    }
    void dfs(int depth,int[] Info,int idx ){
        if(depth==maxDepth){          
            int diff=infoValueDiff(Info);          
            if(diff>maxValue){
                maxValue = diff;
                lInfo = Info;
            }else if(maxValue!=0&&diff==maxValue){
                if(infoDiff(Info)){
                    lInfo = Info;
                }else{
                    return;
                }
            }
            return;
        }
        
        for(int i=idx;i<11;i++){
            int[] newInfo = Info.clone();
            
            if(i==10){
                newInfo[i]+= maxDepth - depth;
                dfs(maxDepth,newInfo,i);
            }else if(maxDepth -depth > aInfo[i]){
                newInfo[i] += aInfo[i]+1;
                dfs(depth+newInfo[i],newInfo,i);
            }
            
        }
          
    
    }
}

이런 방식 말고도 list를 이용해 dfs의 값 newInfo가 같은 형태로 들어오면 dfs를 포기하는 방식으로도 문제가 해결될것같다.