[JAVA] 프로그래머스 양궁대회_구현

 

문제 : 

 

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

프로그래머스

 

 

문제 설명 : 

 

  - 어피치가 n 발을 사격한 후 라이언이 n 발을 사격한다.

 

  - 양궁의 과녁판은 0 ~ 10 점까지 구역별로 존재한다.

 

  - 만약, 10점에 라이온과 어피치가 같은 화살을 맞추면 어피치가 10점을 획득한다.

 

  - 만약, 5 점에 라이온만 맞춘다면 해당 점수에 맞춘 화살의 갯수가 라이온이 더 많으므로 해당 점수를 획득한다.

 

  - 어피치의 화살의 결과를 확인한 후, 점수차가 가장 많이 나도록 라이온이 맞춰야하는 점수를 구한다.

 

 

문제 접근 : 

 

  - 화살은 동일하게 n 발을 쏴야한다.

 

  - 만약 동일하게 n 발을 맞추면 0점이며 n+1 를 초과하는 화살을 맞추면 점수를 더 획득 할 수 없으므로 최대의 점수차가 나지 않는다.

 

  - 이길 수 있는 경우가 다양하고, 특정한 룰을 찾기 어려움으로 가능한 점수를 만들고 확인하면서 점수차를 최대로 갱신한다.

 

 

코드 구현 : 

 

public class Solution {
    private int[] temp;
    private int[] answer;
    private int max_diff;

    public void checkScore(int[] info) {
        int apeach=0;
        int lion=0;

        for(int i = 0; i< temp.length; i++) {
            if(info[i] < temp[i]) lion += 10-i;
            if(info[i]!=0 && info[i]>= temp[i]) apeach += 10-i;
        }

        int diff = lion - apeach;
        if(max_diff <= diff){
            max_diff = diff;
            answer = temp.clone();
        }
    }

    public void dfs(int depth, int n, int[] info) {
        if(depth==n) {
            checkScore(info);
            return;
        }
        for(int i=0; i < info.length ; i++) {
            //만약 현재 스코어의 화살 수가 이미 어피치보다 많다면 탐색 중단
            if(temp[i] > info[i]) break;
            temp[i] += 1;
            dfs(depth+1, n, info);
            temp[i] -= 1;
        }
    }

    public int[] solution(int n, int[] info) {
        temp = new int[info.length];
        max_diff = 0;
        dfs(0, n, info);
        return max_diff == 0 ? new int[]{-1} : answer;
    }
}