프로그래머스 Lv2 양궁대회 문제

• 프로래머스 Lv2 양궁대회 문제
  • 문제를 읽고 난 후의 분석
    • 라이언은 전 챔피언이고 대회 측은 기왕이면 새 챔피언이 나오는 것을 선호
    • 전 챔피언과 도전자가 같은 점수 + 다른 횟수로 과녁을 적중했다면 더 많이 맞힌 쪽에 그 점수가 1번 들어감
    • 전 챔피언과 도전자가 같은 점수 + 같은 횟수로 과녁을 적중했다면 도전자에게 그 점수가 1번 들어감
    • 만약 최종 점수가 같다면 도전자에게 우승이 돌아감
      • 이 문제는 전 챔피언에 대한 것을 결과로 원하므로 지거나 비기면 '-1' 반환
    • 점수는 0~10까지 존재하며 각 선수는 n번 화살을 발사
    • info는 10~0까지의 점수를 나타내는 배열이며 각 요소는 해당 위치(점수)에 적중한 횟수를 나타냄
      • 길이는 11
      • 인덱스는 점수를 의미하며 내림차순
    • 만약 가장 큰점수로 이기는 플랜이 여러 개 라면 가장 낮은 점수를 더 많이 맞힌 경우로 반환
  • 해당 문제의 난이도 상승 원인
    • n이 큰 수가 되었을 떄 경우의 수가 매우 많아짐
  • 해당 문제를 해결한 방법
    • DFS 방식을 사용하여 모든 경우의 수를 구하고 최대차이 + 낮은 점수 위주의 사용 경우를 찾음
  • 해당 문제를 해결였던 과정
    • 여러번 맞혀도 결국 점수를 얻는건 1번 분량의 점수
    • 그리고 라이언이 info를 보고 어떻게 쏴야할지 정하는 문제
    • 그렇다면 '조합식'을 구하는 문제? 조합식을 찾을 수없다면 '-1'하는 문제?
    • 근데 도전자보다 점수를 많이 얻으려면 걔가 맞힌 점수보다 많이 때려야 한다는 건데
    • 그러면 Greedy와 비슷하다고 생각됨
    • 다시 생각하지만 점수는 쟁탈전의 형태 즉, 한 점수는 한 사람에게만 귀속
    • 그러나 Greedy로 해결하기에는 경우의 수가 매우 많아져 이를 모두 체크하면서 실행되는 DFS 방식이 더 적합하다 생각
    • DFS 코드의 구현 부분중 종료 시점의 코드를 작성하기 위해 화살을 모두 사용하거나, 마지막 인덱스에 도달 시 , DFS 재귀함수가 종료되도록 설정하였고 새로 검출된 경우의 수가 현 최대 차이보다 크면 갱신, 최대 점수 - 상대 점수, 현 점수 - 상대 점수의 차가 같다면 더 낮은 경우의 점수를 얻었을 때를 위주로 갱신하여 해결하려 했다.
    • 그러나 코드 작성 후 테스트 케이스 4개를 실행하니 3, 4 번 은 오류로 나와서 확인해보니 현재 나의 코드는 DFS 를 돌 때마다 무조건 화살을 쏘도록 되어있어 화살을 쏘지 않는다는 상황은 고려를하지 않아 이를 추가 후 다시 테스트 하니 4개의 테스트 케이스가 정답으로 표시되어 코드를 제출 후 정답인 것을 확인 함
  • 문제의 핵심
    • DFS로 문제를 해결하는 것
    • 무조건 화살을 쏘는게 아닌, 안 쏘는 상황도 고려해야하는 것
    • 모든 경우의 수를 체크하는게 정확성 면으로는 맞지만 이 검사를 줄일 수 있다면 줄이는 것

public class Lv2Archery {
    public static void main(String[] args){
        int n = 10;
        int[] info = {0, 0, 0, 0, 0, 0, 0, 0, 3, 4, 3};

        for(int i : solution(n, info)){
            System.out.print(i + ", ");
        }
    }

    static int[] resultArr;
    static int resultDist;
    static int[] otherArr;

    public static void dfs(int n, int[] info, int cuurOperIdx){
        if(n == 0 || cuurOperIdx == 11){
            if(n > 0){
                info[info.length - 1] += n;
            }

            int resultSum = 0;
            int otherSum = 0;

            for(int i = 0; i < info.length; i++){
                if(info[i] == 0 && otherArr[i] == 0) continue;
                else if(info[i] > otherArr[i]) resultSum += 10 - i;
                else otherSum += 10 - i;
            }

            int dist = resultSum - otherSum;

            if(dist > 0){
                if(dist > resultDist){
                    resultDist = dist;
                    resultArr = info.clone();
                }
                else if(resultDist == dist){
                    for(int i = info.length - 1; i >= 0; i--){
                        if(info[i] > resultArr[i]){
                            resultArr = info.clone();
                            break;
                        }
                        else if(resultArr[i] > info[i]) break;
                    }
                }
            }

            if(n > 0){
                info[info.length - 1] -= n;
            }

            return;
        }

        dfs(n, info, cuurOperIdx + 1);

        int weight = otherArr[cuurOperIdx] + 1;
        if(weight <= n){
            info[cuurOperIdx] += weight;
            n -= weight;
            dfs(n, info, cuurOperIdx + 1);
            // 백트래킹
            n += weight;
            info[cuurOperIdx] -= weight;
        }

    }

    public static int[] solution(int n, int[] info) {
        resultArr = new int[]{-1};
        resultDist = 0;
        otherArr = info;

        dfs(n, new int[11], 0);

        return resultArr;
    }
}