[Lv.2] 양궁 대회 - JavaScript

문제

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

프로그래머스

 

풀이

재귀 DFS로 풀었고,

1. 라이언이 화살을 쏘는 경우 (라이언이 점수 획득)

2. 라이언이 화살을 쏘지 않는 경우 (어피치가 점수 획득 / 둘 다 쏘지 않음)

로 나눠서 풀었다.

 

과녁의 끝에 도달했을 때에는,

라이언과 어피치의 점수차가 현재의 최댓값보다 큰 경우에만

최대 점수 차이, 라이언의 과녁판을 갱신해주었다.

 

!!! 점수가 가장 낮은 과녁판부터 살펴봐야 한다..!!!

 

코드

function solution(n, info) {
  var answer = [];
  let maxDiff = 0;
  let visited = new Array(11).fill(0);
  
  const DFS = (i, arrow, ryan, peach, visited) => {
    if (i === -1) {
      // 라이언과 어피지 점수를 비교해서 가장 큰 값으로 갱신한다.
      let diff = ryan - peach;
      if (diff > maxDiff) {
        // 남은 화살은 가장 낮은 점수의 과녁에 처리해준다.
        visited[10] = arrow
        // 최댓값 갱신
        maxDiff = diff;
        // 라이언의 과녁을 answer에 저장
        answer = visited;
      }
      return;
    }

    // 1. 화살을 쏠 수 있는 경우
    if (arrow > info[i]) {
      let tmp = [...visited];
      tmp[i] = info[i] + 1;
      // 화살 사용 - 무조건 이겨야하니까 한발 더 쏴준다.
      // 라이언은 과녁판의 점수를 획득한다.
      DFS(i - 1, arrow - info[i] - 1, ryan + 10 - i, peach, tmp);
    }

    // 2. 쏠 수 없거나 그냥 쏘지 않는 경우

    // 어피치의 화살이 있을 때에는 어피치가 점수를 획득한다.
    if (info[i] > 0) DFS(i - 1, arrow, ryan, peach + 10 - i, visited);
    // 둘 다 쏘지 않은 경우에는 누구도 점수를 획득하지 않는다.
    else DFS(i - 1, arrow, ryan, peach, visited);
  };

   // 점수가 낮은 영역부터 탐색한다.
    DFS(10, n, 0, 0, visited);

  return maxDiff ? answer: [-1];
}