프로그래머스 - 양궁 대회

링크

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

---

문제 간단하게 설명 및 분석

카카오배 양궁대회가 열렸다. 과녁판에 라이언과 어피치가 화살을 쏴서 높은 점수를 받는 사람이 이기는 게임이다. 매개변수로 화살의 개수와 어피치가 맞힌 과녁 점수의 개수를 10점부터 0점까지 순서대로 담은 info 배열이 주어진다. 이때 라이언이 어피치를 가장 많은 점수차로 이기는 경우를 배열로 반환하는 문제이다. 근데 여기서 높은 점수를 받는 조건에 대해서 정확히 짚고 넘어가야 한다.

1. 라이언이 이길 수 없는 경우 -1 return
2. k점에 대해서 어피치가 a발 라이언이 b발 맞혔을 때 a>=b 인 경우 어피치 승리, a < b인 경우 라이언의 승리이다.
3. 어피치보다 k점을 여러 발 맞혀 라이언이 승리해도 그냥 k점만 가져가는 것임.
4. k점에 대해 a = b = 0 인 경우 아무도 점수를 못가져간다.
5. 최종적으로 각자 가져간 점수를 합산하여 라이언이 어피치보다 많은 점수차로 이기는 경우를 구해야 함.
6. 이때, 라이언이 가장 큰 점수차로 이길 수 있는 경우가 여러가지인 경우를 생각해야 함.
7. 해당 경우에서는 가장 낮은 점수를 더 많이 맞힌 경우를 리턴해야 한다.
8. 가장 낮은 점수를 맞힌 개수가 똑같으면, 계속해서 그다음으로 낮은 점수를 똑같이 비교한다.
9. 최종 결과값(화살 n발을 어떤 과녁 점수에 몇개씩 맞혔는지) 배열을 리턴

---

어떻게 풀지..?

딱, 느낌은 완전탐색으로 주어진 화살의 개수를 분배해서 모든 경우에 대해서 다 따져보면 될 것 같다는 생각이 들었는데, 솔직히 어떻게 구현할지 막막했다. 내 구현력은 도대체 언제 성장하지..? 그래서 검색찬스 써서 찾아보니 n개의 화살을 배열에 분배할 수 있고, 분배한 인덱스에 중복해서 넣을 수 있는 조합은 중복조합이다.
그래서 최악의 경우 n은 최대 10, 배열의 크기가 11로 고정이므로 10H11이므로
총 184,756의 경우의 수로 안전범위이다.

1. 중복조합으로 화살 분배
2. 화살을 n개만큼 분배했으면 검증
   2-1. 라이언이 얻은 점수, 어피치가 얻은 점수 비교
   2-2. 두 점수의 차(diff)와 maxDiff를 비교
   2-3. diff와 maxDiff가 같다면 낮은 점수를 더 많이 맞춘 경우를 찾는다.
   2-3. diff가 더 가장 낮은 점수를 많이 맞췄다면 diff 배열의 값을 최종정답배열 (finalAnswer로 복사)
3. maxDiff가 0 이라면, 라이언이 어피치보다 높은 점수를 받은 경우가 아예 없는 것이므로 -1 리턴
4. 최종, finalAnswer 배열 리턴

---

구현

import java.util.*;

class Solution {
    
    public int maxDiff = 0;
    public int[] finalAnswer = new int[11];
    
    public int[] solution(int n, int[] info) {
        int[] answer = new int[11];
        select(0, 0, answer ,info, n);
        
        if (maxDiff == 0) {
            answer = new int[1];
            answer[0] = -1;
            return answer;
        }
        
        return finalAnswer;
    }
    
    
    public void select(int idx, int count, int[] answer, int[] info, int n) {
    	// 화살의 개수를 n개만큼 분배 완료했다면
        if (count == n) {
            
            // lion이 얻은 점수, apeach가 얻은 점수
            int lion = 0;
            int apeach = 0;
            
            for (int i = 0; i<=10; i++) {
            	// 과녁 i에 대해서 둘다 하나도 못 맞췄다면 비교 X
                if (answer[i]==0 && info[i]==0) {
                    continue;
                }
                
                // i = 0 -> 10점 과녁이므로 점수를 합산할 때 10-i로 합산
                if (answer[i]>info[i]) {
                    lion += 10 - i;
                }
                if (answer[i]<=info[i]) {
                    apeach += 10 - i;
                }
            }
            
            // 점수차
            int diff = lion - apeach;
            
            // 라이언이 어피치보다 점수가 낮거나 같은 경우 비교할 필요 X
            if (diff <= 0) {
                return;
            }
            
            else {
            	// 이미 저장된 maxDiff보다 낮으면 비교 X
                if (diff < maxDiff) {
                    return;
                }
                
                // 같다면 가장 낮은 점수의 과녁부터 누가 더 많이 맞췄는지 비교한다.
                if (diff == maxDiff) {
                    for (int i = 10; i>=0; i--) {
                    	// 여기서 걸리면 갱신
                        if (answer[i]>finalAnswer[i]) {
                        	// 배열 복사
                            for (int j = 0; j<=10; j++) {
                                finalAnswer[j] = answer[j];
                            }
                            return;
                        }
                        // 여기서 걸리면 finalAnswer배열이 가장 낮은 점수의 과녁을 더 많이 맞춤
                        if (answer[i]<finalAnswer[i]) {
                            return;
                        }
                    }
                    return;
                }
                
                if (diff > maxDiff) {
                    maxDiff = diff;
                    for (int i = 0; i<=10; i++) {
                        finalAnswer[i] = answer[i];
                    }
                    return;
                }
                
            }
            return;
        }
            
        // 중복조합으로 배열에 값을 할당한다.
        // 백트래킹으로 풀었다.
        for (int i = idx; i<=10; i++) {
        	/*과녁 i에 대해 라이언이 쏜 화살수가 어피치가 쏜 화살수보다 
            많으면 이미 라이언이 이긴 경우이므로 더 이상 계산할 필요 없다.*/
            if(answer[i]>info[i]) {
                continue;
            }
            answer[i]++;
            select(i, count+1, answer, info, n);
            answer[i]--;
        }
    }
}