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

---

문제 생략

풀이

import java.util.*;
import java.lang.*;
// 각 점수를 받거나 포기하거나
class Solution {
    static int finalScore = Integer.MIN_VALUE; // 라이언 최종 점수
    static int[] scores; // 최종 점수판 
    static int[] result;  // 임시 점수판
    public int[] solution(int n, int[] info) {
        scores= new int[]{-1}; 
        if(info[0] == n )
            return scores;
        result = new int[info.length];
        
        get(0, n, info);
        return scores;
    }
    // 부분조합 / 매개변수: 인덱싱용 idx, 남은 화살, 어피치 점수판
    public static void get(int idx, int restArrow, int[] info){
        // 기저조건: 과녁 별 점수 결정 끝
        result[10] += restArrow; // 남은 화살 0번 과녁에 몰빵
        if(idx >= 11){
            // 라이언의 점수 세기
            int ryanSum = 0;
            int apeachSum = 0;
            for(int i=0; i<11; i++)
                if(result[i] > info[i])
                    ryanSum += 10-i;
                else if(info[i] >= result[i] && info[i]!=0)
                    apeachSum += 10-i;
                
            // 라이언이 어피치보다 많이 쏨
            if(ryanSum <= apeachSum) return;
            
            if(ryanSum - apeachSum > finalScore){ // 최종점수, 점수판 기록
                finalScore = ryanSum - apeachSum; 
                scores = Arrays.copyOf(result, result.length);
            }
            else if (ryanSum - apeachSum == finalScore){ // 작은 걸 더 많이 맞춘 점수판으로 기록
                for(int i=10; i>=0; i--){
                    if(result[i] > scores[i]){
                        scores = Arrays.copyOf(result, result.length);
                        break;
                    } else if (scores[i] > result[i]) break;
                }
            }
            return;
        } 
        
        // 점수를 받거나 포기하거나
        if(restArrow > info[idx]){ // 득점
            result[idx] = info[idx]+1;
            get(idx+1, restArrow-result[idx], info);
        } 
        result[idx] = 0; // 포기
        get(idx+1, restArrow, info);
    }
}

풀이는 간단하다. 핵심은 각 과녁에서 점수를 받거나 포기하거나이다.

그래서 부분조합을 응용해서 풀었다.

 // 점수를 받거나 포기하거나
if(restArrow > info[idx]){ // 득점
    result[idx] = info[idx]+1;
    get(idx+1, restArrow-result[idx], info);
} 
result[idx] = 0; // 포기
get(idx+1, restArrow, info);

부분조합의 핵심

이 문제는 문제를 해결하기 위한 발상(?) 이 중요하기 보다 예외처리가 훨씬 중요한 문제였다.

예외처리를 위한 흔적들

result[10] += restArrow; // 남은 화살 0번 과녁에 몰빵

화살이 남으면 0번 과녁에 몰빵해서 라이언이 가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지 일 경우, 가장 낮은 점수를 더 많이 맞힌 경우를 return 조건에 대처한다.

---

 // 라이언이 어피치보다 많이 쏨
if(ryanSum <= apeachSum) return;

라이언이 어피치보다 적게 쏘는 경우가 계속 되면 [-1]이 리턴될 것이다.

---

if(ryanSum - apeachSum > finalScore){ // 최종점수, 점수판 기록
    finalScore = ryanSum - apeachSum; 
    scores = Arrays.copyOf(result, result.length);
}
else if (ryanSum - apeachSum == finalScore){ // 작은 걸 더 많이 맞춘 점수판으로 기록
    for(int i=10; i>=0; i--){
        if(result[i] > scores[i]){
            scores = Arrays.copyOf(result, result.length);
            break;
        } else if (scores[i] > result[i]) break;
    }
}

라이언이 가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지 일 경우, 가장 낮은 점수를 더 많이 맞힌 경우를 return 조건을 충족하는 부분.
참고로 else if (scores[i] > result[i]) break; 를 쓰지 않아 시간이 많이 걸렸다.

---

결과

후기

예외처리를 할 때 정신을 바짝 차리고 해야한다!
다 했다고 방심 금지, 또한 반례를 설정해 모든 테스트케이스를 시도해 볼 것

보너스

질문게시판에서 주워온 반례를 이용하면 라이언이 가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지 일 경우, 가장 낮은 점수를 더 많이 맞힌 경우를 return 조건 처리에 도움이 된다

3, [0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1], [1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0]