풀이 Logic

완전 탐색과 깊이 우선 탐색(DFS)을 사용하여 모든 가능한 경우를 탐색합니다.
DFS 함수는 각 점수(10점부터 0점까지)에 대해 라이언이 화살을 쏠지 말지를 결정합니다.
모든 화살을 사용했거나 마지막 점수(0점)에 도달하면, 라이언과 어피치의 점수를 계산합니다.
라이언이 이기는 경우 중 가장 큰 점수 차이를 찾고, 그때의 화살 배치를 저장합니다.
점수 차이가 같은 경우, 가장 낮은 점수에 더 많은 화살을 쏜 경우를 선택합니다.

해답 코드

function solution(n, info) {
  let max = 0;
  let answer = [-1];
  let ryan = Array(11).fill(0);
 
  function DFS(level, count) {
    // 기저 조건(base case)
    if (level == 11 || count == 0) {
      if (count > 0) ryan[10] += count; // 마지막에 남은 화살이 있다면 0점에 할당하고, 계산 후 다시 제거합니다.
 
      let sum = 0;
      for (let i = 0; i < 11; i++) {
        if (ryan[i] > info[i]) {
          // ryan이 apeach보다 해당 level에서 더 많이 맞춘 경우
          sum += 10 - i;
        } else if (info[i] > 0) {
          // 해당 level에서 ryan보다 더 많이 맞췄거나, 같은 화살 수인 경우
          sum -= 10 - i;
        }
      }
 
      if (sum > 0 && sum >= max) {
        if (sum > max || isLowerScoreBetter(ryan, answer)) {
          max = sum;
          answer = [...ryan];
        }
      }
 
      if (count > 0) ryan[10] -= count;
      return;
    }
 
    // ryan이 가지고 있는 화살 수가 apeach가 해당 level에서 맞힌 화살 수보다 많은 경우
    if (count > info[level]) {
      ryan[level] = info[level] + 1;
      DFS(level + 1, count - ryan[level]);
      ryan[level] = 0; // 백트래킹  -  이전 단계로 되돌아감
    }
 
    DFS(level + 1, count);
  }
 
  function isLowerScoreBetter(ryan, answer) {
    for (let i = 10; i >= 0; i--) {
      // 가장 낮은 점수를 더 맞이 맞힌 경우 (문제 조건)
      if (ryan[i] !== answer[i]) {
        return ryan[i] > answer[i];
      }
    }
    return false;
  }
 
  DFS(0, n);
  return answer;
}

코드 해설

백트래킹

ryan[level]을 통해서 이전 단계로 되돌아감으로써

if (count > info[level]) {
  ryan[level] = info[level] + 1;
  DFS(level + 1, count - ryan[level]);
  ryan[level] = 0; // 백트래킹  -  이전 단계로 되돌아감
}

isLowerScoreBetter 함수

function isLowerScoreBetter(ryan, answer) {
  for (let i = 10; i >= 0; i--) {
    // 가장 낮은 점수를 더 맞이 맞힌 경우 (문제 조건)
    if (ryan[i] !== answer[i]) {
      return ryan[i] > answer[i];
    }
  }
  return false;
}

가장 낮은 점수를 더 맞이 맞힌 경우 (문제 조건) 에 의해서 i가 10부터 0까지 돈다. i가 10일 경우 문제에서 10점이라고 하였기 때문에.

다듬기 전 코드

function solution(n, info) {
  var answer = [-1];
 
  let max = 0;
  let ryan = new Array(info.length).fill(0);
 
  function dfs(level, arrow) {
    // 기저 조건
    if (level === 11 || arrow === 0) {
      if (arrow > 0) ryan[10] += arrow;
 
      let sum = 0;
      for (let i = 0; i < info.length; i++) {
        if (ryan[i] > info[i]) {
          // ryan[i] <= info[i] 이건 둘 다 0점일 경우도 포함되기 때문에 안됌
          sum += 10 - i;
        } else if (info[i]) {
          sum -= 10 - i;
        }
      }
 
      if (sum > 0 && sum > max) {
        max = sum;
        answer = [...ryan];
      } else if (sum > 0 && sum === max) {
        for (let i = 10; i >= 0; i--) {
          if (ryan[i] !== answer[i]) {
            if (ryan[i] > answer[i]) {
              max = sum;
              answer = [...ryan];
            }
            break;
          }
        }
      }
 
      if (arrow > 0) ryan[10] -= arrow;
      return;
    }
 
    if (arrow > info[level]) {
      ryan[level] = info[level] + 1;
      dfs(level + 1, arrow - ryan[level]);
      ryan[level] = 0;
    }
 
    dfs(level + 1, arrow);
  }
 
  dfs(0, n);
 
  return answer;
}