[프로그래머스] 카카오 기출 - 양궁대회

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

프로그래머스

 

 

풀이

n의 범위가 10으로 아주 작아 완전탐색으로 풀이가 가능하다.
하지만 완전탐색 돌릴시 시간초과가 날 수 있기 때문에 몇가지 주의사항이 필요하다

1. 유망한 조건에 대해서만 반복하기 
   ->  dfs 내에서 for문을 돌릴 때 현재 라이언이 어피치보다 화살을 맞춘 갯수가 많으면 더 이상 돌릴필요가 없다.

2. 점수 계산시 0점은 제외하기
   -> 0점은 계산해봤자 의미가 없기때문에 제외시켜준다.
   -> 유의미한 차이가 발생할 수 있다.

그리고 마지막으로 리턴할 배열에 대해서는 깊은복사가 필요하다
얕은복사(주소값만 복사)로 값을 넣어줄 경우 해당 주소값의 값이 계속 변할경우 같이 변하기때문에
제대로 된 정보를 리턴해줄 수 없다.

카카오 기출은 재밌다ㅏㅏㅏㅏㅏㅏ

class Solution {

    private int N;
    private int[] apeachTarget;
    private int[] lionTarget;
    private int max = 0;
    private int[] answer;
    public int[] solution(int n, int[] info) {
        N = n;
        apeachTarget = info;
        lionTarget = new int[11];

        dfs(0, lionTarget);
        System.out.println(max);

        return max == 0 ? new int[]{-1} : answer;

    }

    private void dfs(int depth, int[] lionTarget) {

        if (depth == N) {
            int score = getDiffScore(lionTarget);
            if (score >= max) {
                max = score;
                answer = lionTarget.clone();
            }
            return;
        }

        for (int i = 0; i < 11; i++) {
            if (apeachTarget[i] < lionTarget[i]) break;

            lionTarget[i]++;
            dfs(depth + 1, lionTarget);
            lionTarget[i]--;
        }

    }

    private int getDiffScore(int[] lionTarget) {

        int apeachScore = 0;
        int lionScore = 0;

        for (int i = 0; i < 10; i++) {
            if (lionTarget[i] > apeachTarget[i]) lionScore += (10 - i);
            else if (apeachTarget[i] != 0) apeachScore += (10 - i); 
        }

        return apeachScore > lionScore ? 0 : lionScore - apeachScore;

    }


}