Programmers 92342 - 양궁대회

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

프로그래머스

 

라이언(우승자), 어피치(도전자)

어피치가 먼저 n발을 쏜 후 라이언이 화살 n발을 쏜다.

k(1 ~ 10)점을 어피치가 a발맞추고 라이언이 b발맞춘 경우 더 많은 화살을 k점에 맞힌 선수가 k점을 가져간다. 단, a = b 일 경우는 어피치가 k점을 가져한다.

k점을 많이 맞춘다고 k점 보다 많은 점수를 가져가는게 아니라 k점만 가져한다.

모든 결과가 나왔을 때 최종 점수가 더 높은 선수를 우승자로 결정한다. 단, 최종 점수가 같을 경우 어피치가 우승한다.

현재 상황은 어피치는 이미 n발을 다 쐈고 라이언이 n발을 쏠 차례이다.

라이언이 가장 큰 점수 차이로 이기기 위해서 n 발의 화살을 어떤 과녁 점수에 맞혀야 하는가. 만약 라이언이 우승할 수 없는 경우 [-1]을 return

라이언이 가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지 일 경우, 가장 낮은 점수를 더 많이 맞힌 경우를 return

 

점수가 10~0점 까지 있다. 라이언이 해당 점수를 가져갈지 말지를 결정하는 문제이다.

해당 점수를 가져가려면 어피치가 맞춘 개수 + 1 개를 맞춰야 한다.

그렇다면 완전탐색을 통해서 모든 경우의 수를 확인하면 된다. 여기서 변하는 값은 표적의 인덱스와 남은 화살의 개수가 될 것이다.

화살이 0개 미만이 되면 더 이상 선택을 할 수 없어진다.

그런데 가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지 일 경우의 조건을 해결해야 한다.

만약 점수 차이가 갱신이 되면 해당 배열을 저장한다. 점수 차이가 동일하다면 두 배열을 비교해 낮은 점수가 많은 배열을 선택해서 저장한다.

import java.util.*;

class Solution {
    
    static int maxScoreGap = Integer.MIN_VALUE;
    static int[] answer = {};
    
    public int[] solution(int n, int[] info) {
        int[] ryan = new int[11];
        dfs(0, n, ryan, info);
        
        return maxScoreGap <= 0 ? new int[]{-1} : answer;
    }
    
    private void dfs(int idx, int n, int[] ryan, int[] apeach) {
        if (n == 0 || idx == 11) {
            // 모든 화살을 쐈거나, 마지막 과녁까지 끝났다.
            int gap = calculateGap(ryan, apeach);
            int[] copiedRyan = ryan.clone();
            copiedRyan[10] += n; // 마지막 과녁까지 했는데 화살이 남은 경우 0점에 몰아준다.
            if (maxScoreGap < gap) {
                answer = copiedRyan;
                maxScoreGap = gap;
            } else if (maxScoreGap == gap) {
                compareResult(copiedRyan);
            }
            return;
        }
        
        // 획득 가능하며 해당 점수 획득
        if (n >= apeach[idx] + 1) {
            ryan[idx] = apeach[idx] + 1;
            dfs(idx + 1, n - ryan[idx], ryan, apeach);
            ryan[idx] = 0; 
        }
        // 해당 점수 패스
        dfs(idx + 1, n, ryan, apeach); 
    }
    
    private int calculateGap(int[] ryan, int[] apeach) {
        int ryanScore = 0;
        int apeachScore = 0;
        for (int i = 0; i < 11; i++) {
            if (ryan[i] == 0 && apeach[i] == 0) {
                continue;
            }
            
            if (ryan[i] > apeach[i]) {
                ryanScore += 10 - i;
            } else {
                apeachScore += 10 - i;
            }
        }
        return ryanScore - apeachScore;
    }
    
    private void compareResult(int[] ryan) {
        // answer와 ryan을 비교해서 낮은 점수가 더 많은 경우
        for (int i = 10; i >= 0; i--) {
            if (ryan[i] > answer[i]) {
                answer = ryan.clone();
                break;
            } else if (ryan[i] < answer[i]) {
                break;
            }
        }
    }
    
}