[Programmers-Java] 양궁대회

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

접근

라이언의 화살을 dfs 탐색한다.
과녁에 맞췄지만 어피치보다 개수가 적어서 점수를 얻지 못하는 경우도 탐색해야 한다.
어피치의 총 점수를 구하고 라이언의 점수를 빼 나간다.

풀이

import java.util.*;

class Solution {
    private int[] ryan = new int[11];
    private int[] apeach;
    private List<int[]> candidates = new ArrayList<>();
    private int maxDiff;

    public int[] solution(int n, int[] info) {
        this.apeach = info;
        dfs(n, 0, -getApeachScore());

        if (maxDiff == 0) {
            return new int[] {-1};
        }
        return selectRyan();
    }

    private int getApeachScore() { // (1)
        int score = 0;
        for (int i = 0; i < 11; i++) {
            if (apeach[i] > 0) {
                score += 10 - i;
            }
        }
        return score;
    }

    private void dfs(int arrow, int i, int scoreDiff) {
        if (arrow == 0) { // (2)
            registerCandidate(scoreDiff);
            return;
        }
        if (i == 11) { // (3)
            return;
        }

        for (int cnt = apeach[i] + 1; cnt > -1; cnt--) { // (4)
            ryan[i] = cnt;
            dfs(arrow - cnt, i + 1, calculateScoreDiff(i, scoreDiff));
            ryan[i] = 0;
        }
    }

    private int calculateScoreDiff(int i, int prevScoreDiff) {
        if (ryan[i] <= apeach[i]) { // (5)
            return prevScoreDiff;
        }
        if (apeach[i] == 0) { // (6)
            return prevScoreDiff + (10 - i);
        }
        return prevScoreDiff + (10 - i) * 2; // (7)
    }

    private void registerCandidate(int scoreDiff) { // (8)
        if (scoreDiff < maxDiff) {
            return;
        }

        if (scoreDiff > maxDiff) {
            maxDiff = scoreDiff;
            candidates.clear();
        }
        candidates.add(ryan.clone());
    }

    private int[] selectRyan() { // (9)
        for (int i = 10; i > -1; i--) {
            if (candidates.size() == 1) {
                break;
            }

            int maxArrow = 0;
            List<int[]> tmp = new ArrayList<>();
            for (int[] candidate : candidates) {
                if (candidate[i] > maxArrow) {
                    maxArrow = candidate[i];
                    tmp.clear();
                    tmp.add(candidate);
                } else if (candidate[i] == maxArrow) {
                    tmp.add(candidate);
                }
            }
            candidates = tmp;
        }
        return candidates.get(0);
    }
}