백트래킹

라이언을 억까하는 양궁대회이다.

우선 처음에 그리디 알고리즘으로 풀어보려 했다. 쏜 화살 갯수 대비 가장 효율이 좋은, (획득점수/쏴야되는화살갯수)가 높은 순으로 쏜 결과를 구하려 했는데, 생각해보니 해당 과녁에 점수를 쏘았을 때, 어피치가 점수를 획득하냐 라이언이 점수를 획득하냐에 따른 우선순위를 고려할 수 없었다. 따라서 중복조합 으로 풀어야 한다. 과녁도 10칸이고 화살은 10개 이하로 쏘기 때문에 시간초과가 나지 않는다.

1. 11개짜리 배열을 만들어서, 총 화살 갯수를 분배하는 중복 조합을 탐색한다.

2. 만들어진 중복조합 중 라이언과 어피치의 점수차가 가장 큰 경우, 점수차가 같은 조합이 두개 이상이라면 낮은 화살에 많이 맞은 경우를 찾는다.

3. 만들어진 중복조합에서 라이언이 어피치를 이길 수 없다면 [-1] 을 리턴한다.

/*

조건)

라이언은 불리하게 게임 함
더 많은 화살을 k 점에 맞힌 선수가 k 점을 획득
두 선수가 같은 점수의 과녁에 같은 발을 맞췄다면 어피치가 이김
둘다 k 점에 맞히지 못한 경우 둘 다 0점

결과 판별)
최종 점수를 비교, 어피치>=라이언 일 경우 어피치가 우승

목표)
라이언이 가장 큰 점수차로 이기기 위해 n 발의 화살을 각각 어느 과녁 점수에 맞혀야 하는지 구하기
[10점,9점,8점,7점,6점,5점,4점,3점,2점,1점,0점] 순으로 리턴

가장 큰 점수차가 나오는 방법이 여러 가지 인 경우 가장 낮은 점수를 더 많이 맞힌 경우로 리턴

라이언이 우승할 수 없는 경우 [-1]
*/


/*
Sol1) 그리디 -> 화살 개수 대비 가장 점수를 많이 획득하는 순으로 쏘기

- > 반례가 있음. (2발 쏴서 얻는 점수 < 1발씩 두번 쏘는 점수 인 경우)
Sol2) 모든 중복조합으로 조회
과녁의 점수는 11가지, 화살의 갯수는 10 이하이므로 시간초과 나지 않음

*/

import java.util.*;
class Solution {
    static ArrayList<int[]> shoots = new ArrayList<>();
    public int[] solution(int n, int[] info) {
        dfs(0, n, 0, new int[11]);

        int[] answer = new int[11];
        int max=0;
        for(int[] ryan : shoots){      // 라이언의 정보

            int ryanPoint = 0;
            int apeachPoint = 0;
            for(int i=0;i<11;i++){

                // 둘 다 맞히지 못한 과녁 = 둘 다 0점
                if(ryan[i]==0 && info[i]==0){
                    continue;
                }
                // 과녁의 점수에서 라이언이 더 많이 맞췄다면
                if(info[i]<ryan[i]){
                    ryanPoint+=10-i;
                }

                // 과녁의 점수에서 어피치가 더 많거나 같게 맞췄다면
                else{
                    apeachPoint+=10-i;
                }
            }

            int diff = ryanPoint-apeachPoint; // 해당 조합에서 라이언과 어피치의 점수차이

            if(diff<=0){
                continue;
            }
            if(max<diff){
                
                max=diff;
                answer=ryan.clone();
            }
            
            if(max==diff){      // ryan = 새로 들어온 조합, answer = 기존 조합
                for(int i=10;i>=0;i--){
                    if(ryan[i]>answer[i]){
                        answer=ryan.clone();
                        break;
                    }
                    else if(ryan[i]==answer[i]){
                        continue;
                    }
                    else{
                        break;
                    }
                }
            }
        }
        
        // max 가 0 인 경우(라이언이 지거나 비기는 경우만 있음)
        if(max==0){
            return new int[]{-1};
        }
        return answer;
        
    }
    
    // 모든 중복 조합을 추가해주는 메소드
    public static void dfs(int shot, int n, int index, int[] result){
        if(shot == n){
			// 깊은 복사로 static arraylist에 추가
            int[] data = result.clone();
            shoots.add(data);
            return;
        }

        // 현재 인덱스에 몇개의 화살을 쏠 것인지
        for(int i = 0 ; i <= n ; i++){
            if(index==result.length){
                return;
            }
            if(shot>n){
                return;
            }

            // 해당 인덱스에 i 개를 쏨
            int prev = result[index];
            result[index]=i;
            dfs(shot+i,n,index+1,result);
            result[index]=prev;
        }
    }
}