programmers Level 2 양궁대회

문제

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

걸린 시간

-

풀이

JavaScript

function solution(n, info) {
    let answer = [-1];
    let candidate = {/*
        key: number,
        value: Array<Array<number>>
    */};
    let max_diff = 0;
    const solve = (idx, r_n, r_info) => {
        // 기저 사례
        if(idx === 11){
            if(r_n){
                // 화살이 남았으면
                r_info[10] += r_n;
            }
            let r_point = 0;
            let a_point = 0;
            for(let i = 0; i < 11; i++){
                if(r_info[i] && info[i]){
                    if(r_info[i] > info[i]) r_point += 10-i;
                    else a_point += 10-i;
                }
                else{
                    if(r_info[i]) r_point += 10-i;
                    if(info[i]) a_point += 10-i;
                }
            }
            let diff = r_point - a_point;
            if(diff > 0){
                max_diff = Math.max(max_diff, diff);
                if(!candidate.hasOwnProperty(diff)) candidate[diff] = [];
                candidate[diff].push([...r_info]);
            }
            return;
        }
        // 재귀 함수
        {
            if(r_n > info[idx]){
                r_info.push(info[idx]+1);
                solve(idx+1, r_n-(info[idx]+1), r_info);
                r_info.pop();
            }
        }
        {
            r_info.push(0);
            solve(idx+1, r_n, r_info);
            r_info.pop();
        }
    }
    solve(0, n, []);
    const arr = [/*
        [
            idx: number,
            n: number,
            info: number[]
        ],
    */];
    if(Object.keys(candidate).length){
        for(let c of candidate[max_diff]){
            for(let i = 10; i >= 0; i--){
                if(c[i]){
                    arr.push([i, c[i], c]);
                }
            }
        }
        arr.sort((a, b) => {
            /*
                a[0] = idx
                a[1] = n
            */
            if(a[0] < b[0]){
                if(a[1] > b[1]) return 1;
                else return 1;
            }
            else return -1;
        });
        answer = arr[0][2];
    }
    return answer;
}

처음에 문제를 그리디로 접근하다 최근에 풀었던 백준 14501번 퇴사 문제와도 접근 방식이 똑같다는 걸 너무 늦게 깨달았다. (코드를 새로 다시 작성했다.)

매 점수마다 어피치보다 더 많은 화살을 쏴서 점수를 획득할지, 맞추지 않고 다른 과녁을 노릴지 판단하면 되는 백트래킹으로 문제이다.

데이터를 어떻게 저장하고 조건에 맞게 정답을 골라야할지도 많이 생각해야 했다.

구현 중 실수

• 배열 info 의 크기를 11 이 아닌 10 으로 생각하고 풀었었다.
• 화살의 개수와 점수를 많이 혼동했다.

해결 과정

1. key 를 점수 차이, value 를 라이언의 info 배열 로 하는 객체 candidate 에 가능한 모든 경우를 재귀를 통해 조사하여 저장한다.
2. 1번 과정에서 최대 점수차이를 max_diff 변수에 누적해 두었다가 candidate[max_diff] 로 접근하여 정답 후보들을 구한다.
3. 후보들 중 "가장 낮은 점수를 더 많이 맞춘" 정답을 골라야 하므로 [낮은 점수의 인덱스, 낮은 점수의 화살 개수, 라이언의 info 배열] 원소로 구성된 배열을 만들어 1, 2 번째 원소를 기준으로 정렬해준 후 맨 첫번째 값을 골랐다.