[프로그래머스][백트래킹] 양궁대회

     

목차

 

 

문제

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

프로그래머스

 

 

코드 구현 방향

백트래킹 시에 마지막 종료 조건 도달 시 처리를 또 해주어야 되는 것과 양궁점수를 확인하는 로직에서 주의를 해야했던 문제이다.

양궁점수의 차가 같을 경우 뒤부터 비교를 시작해서 rion이 더 크면 답으로 하고 멈추고 peach가 더 크면 멈추게끔 하면된다.

 

 

코드 구현

var answer = [-1];

function solution(n, info) {
    let arr = new Array(11).fill(0);
    dfs(n, info, 0, 0, arr);
    return answer;
}

var mGap = -Infinity;

function checking(n, info, arr){
    let peach = 0;
    let rion = 0;
    arr.forEach((item, idx)=>{
        if(item <= info[idx]){
            if(info[idx] !== 0){
                peach += 10 -idx;
            }
        }else{
            rion += 10 - idx;
        }
    })
    let gap = rion - peach;
    if(gap <= 0) return;
    if( mGap < gap){
        mGap = gap;
        answer = [...arr];
    }
  else if ( mGap === gap) {
    for (let i = 10; i >= 0; i--) {
        if (arr[i] > answer[i]) {
            answer = [...arr];
            break;
        } else if (arr[i] < answer[i]) {
            break;
        }
    }
}
    
}

function dfs(n, info, arw, cnt, arr){
    if(cnt === 10 && n >= arw){
        arr[cnt] = n - arw;
        checking(n, info, arr);
        return;
    }
    for(let i=0; i< 2; i++){
        if(i === 0){
            let canWin = info[cnt] + 1;
            if(arw + canWin > n) continue;
            arr[cnt] = canWin;
            dfs(n, info, arw+canWin, cnt+1, arr);
            arr[cnt] = 0;
        }else{
            dfs(n, info, arw, cnt+1, arr);
        }
    }
    
}