[프로그래머스 lev2/JS] 양궁대회

문제 출처

프로그래머스 lev2 - 양궁대회

나의 풀이 (실패)

남은 화살이 없어서 점수를 획득할 때, 어떻게 처리해야 할지가 어려웠다.
⇒ 남은 화살이 없으면 어피치가 점수를 획득하거나 둘다 점수를 획득하지 못하는 경우를 추가하면 된다.

다른 풀이 1

index 0에서 시작해서 재귀를 통해 가지를 뻗어 나간다. (DFS)

하나의 index에서 경우의 수는 3가지이다.
[1] 라이언 점수 획득
[2] 어피치 점수 획득
[3] 둘다 점수 미획득

const solution = (n, info) => {
  let maxDiff = 0;
  let rInfo = Array.from({length:11}, () => 0) 
  
  const dfs = (pScore, rScore, cnt, idx, arr) => {
    if(n < cnt) return // [2][3] 경우의 수로 돌아가야 하므로
    if(idx > 10){ // 끝까지 탐색을 마쳤을 때 점수차를 구해 최대값을 갱신한다. 
      let diff = rScore - pScore;
      if(diff > maxDiff){
        arr[10] = n - cnt; // 끝까지 왔는데도 cnt가 있으면 제일 높은 점수에 할당해버린다. 
        maxDiff = diff
        rInfo = arr;
      }
      return;
    }
    // [1] 라이언이 점수 획득하는 경우
    if(n > cnt) {  
      let dupArr = [...arr];
      dupArr[10 - idx] = info[10 - idx] + 1;
      dfs(pScore, rScore + idx, cnt + info[10 - idx] + 1, idx + 1, dupArr);
    }
    
    // [2] 어피치가 점수 획득하는 경우
    if(info[10 - idx] > 0){  
      dfs(pScore + idx, rScore, cnt, idx + 1, arr)
    } 
    // [3] 둘다 점수 획득 못하는 경우
    else {  
      dfs(pScore, rScore, cnt, idx + 1, arr)
    }
  }
  dfs(0, 0, 0, 0, rInfo)
  
  if(maxDiff <= 0) return [-1];
  else return rInfo;
}

console.log(solution(5, [2, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0])) // [0, 2, 2, 0, 1, 0, 0, 0, 0, 0, 0]
// console.log(solution(1, [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])) // [-1]
// console.log(solution(9, [0, 0, 1, 2, 0, 1, 1, 1, 1, 1, 1])) // [1, 1, 2, 0, 1, 2, 2, 0, 0, 0, 0]
// console.log(solution(10, [0, 0, 0, 0, 0, 0, 0, 0, 3, 4, 3])) // [1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 2]