프로그래머스 양궁대회

풀이

냅색 알고리즘을 이용해 해결했다.
화살의 개수 = 무게
과녁의 점수 = 가치
에 대입해보면 냅색 알고리즘을 적용할 수 있다.

하지만, 주의할점은 이미 피치가 맞춘 과녁의 점수는 점수의 가치가 두배라는 점이다.
(피치는 얻을 점수를 얻지 못하고 라이언이 그 만큼의 점수를 얻기 때문)

또, 냅색에 경로 추적까지 필요하다. 최종 점수가 어떤 과녁을 맞춰서 얻어낸 점수인지 알아야 원하는 배열을 구해낼 수 있기 때문이다.

소스코드

function solution(n, info) {
    let dp = Array.from(Array(12),()=>new Array(12).fill(0));
    let route = Array.from(Array(12),()=>new Array(12).fill([]));//경로 저장을 위한 2차원 배열

    for(let a=1;a<=11;a++){
        let w = info[a-1]+1;//해당 과녁의 점수를 얻기 위해 "피치가 해당 과녁에 맞춘 화살 수 + 1" 개의 화살이 필요
        let v = 10-(a-1);
        let ov = v;
        if(info[a-1]!=0) v*=2;//피치가 맞춘 과녁의 경우 가치가 2배
        for(let b=1;b<=n;b++){
            if(w>b) {
                dp[a][b]=dp[a-1][b];
                route[a][b]=route[a-1][b].slice();
            }
            else {
                if(dp[a-1][b]>dp[a-1][b-w]+v){
                    dp[a][b]=dp[a-1][b];
                    route[a][b]=route[a-1][b].slice();
                }
                else{
                    dp[a][b] = dp[a-1][b-w]+v;
                    route[a][b] = route[a-1][b-w].slice();
                    route[a][b].push(ov);
                }
            }
        }
    }
        
    let peach=0,lion=0;
    for(let i=0;i<info.length;i++){
        if(route[10][n].includes(10-i)){
            lion+=10-i;
        }
        else if(info[i]!=0) peach+=10-i;
    }//최종 점수에 대한 경로에서 lion, peach의 점수를 계산
    if(peach>=lion) return [-1];
  //최종 점수에서 peach 가 lion 의 점수 이상이라면
  //lion이 이길 수 있는 방법이 없는 것이므로 -1 리턴
    
  
  //최종 경로에서 lion이 얻는 점수에 대해
  //몇개의 화살을 사용하는지 res 배열에 담아줌
    let shootCnt = 0;
    let res=[];
    for(let i=10;i>0;i--){
        if(route[10][n].includes(i)){
            res.push(info[10-i]+1);
            shootCnt+=info[10-i]+1;
        }
        else res.push(0);
    }
    
  	//n에서 위의 점수를 모두 얻고 남은 화살들은
  	//0점 과녁에 쏘도록 n-shootCnt 값을 배열에 담아줌
    res.push(n-shootCnt);
    return res;
}

console.log(solution(3,[0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0]));

후기

어려웠다.. ㅎㅎ 풀면서도 이게 lv2 문제가 맞나? 하는 생각이 들었다. 냅색을 적용할 수 있겠다는 생각까지는 금방 미쳤는데 냅색+역추적+구현에 자잘하게 고려할것도 많아서 생각보다 시간이 많이 들었다.

알고보니 범위가 작아 완전 탐색으로 더 쉽게 해결이 가능한 문제였다. 이건 냅색이네 하는 편견에 사로잡혀서 꽤나 지저분하게 해결한 것 같다.