[JAVA] 양궁대회

양궁대회

링크

프로그래머스

 

난이도 : Level 3

유형 : dfs, 백트래킹

코딩테스트 연습 > 2022 KAKAO BLIND RECRUITMENT > 양궁대회

 

풀이

라이언이 어피치를 가장 큰 점수 차이로 이기기 위한 n 발의 화살의 경우의 수를 구하는 문제.

근데 가장 큰 점수 차이의 경우의 수가 여러 가지일 경우, 낮은 점수를 더 많이 맞힌 경우가 정답.

 

각 점수대 마다 라이언이 점수를 가져가냐, 안 가져가냐 둘 중에 하나니까 이걸 그래프로 생각을 해서 dfs로 모든 경우의 수를 보고

가장 큰 점수 차이면서 낮은 점수가 더 많이 맞은 경우를 result에 저장하며 풀었다.

 

코드

class Solution {
    public int maxDiff = 0;
    public int[] result = new int[11];

    public int[] solution(int n, int[] info) {
        int[] ryan = new int[11];
        dfs(0, n, ryan, info);
        return maxDiff > 0 ? result : new int[]{-1};
    }

    public void dfs(int idx, int arrows, int[] ryan, int[] apeach) {
        if (idx == 11 || arrows == 0) {
            ryan[10] += arrows; // 남은 화살은 모두 0점에 추가
            int scoreDiff = calDiff(ryan, apeach);
            if (scoreDiff > maxDiff) {
                maxDiff = scoreDiff;
                result = ryan.clone();
            } else if (scoreDiff == maxDiff) {
                for (int i = 10; i >= 0; i--) {
                    if (ryan[i] > result[i]) {
                        result = ryan.clone();
                        break;
                    } else if (ryan[i] < result[i]) {
                        break;
                    }
                }
            }
            ryan[10] -= arrows; // 백트래킹
            return;
        }

        // 라이언이 해당 점수를 가져가는 경우
        if (arrows > apeach[idx]) {
            ryan[idx] = apeach[idx] + 1;
            dfs(idx + 1, arrows - (apeach[idx] + 1), ryan, apeach);
            ryan[idx] = 0; // 백트래킹
        }

        // 라이언이 해당 점수를 포기하는 경우
        dfs(idx + 1, arrows, ryan, apeach);
    }

    public int calDiff(int[] ryan, int[] apeach) {
        int ryanScore = 0, apeachScore = 0;
        for (int i = 0; i < 11; i++) {
            if (ryan[i] > apeach[i]) {
                ryanScore += (10 - i);
            } else if (apeach[i] > 0) {
                apeachScore += (10 - i);
            }
        }
        return ryanScore - apeachScore;
    }
}