[프로그래머스] 카카오 - 양궁대회

문제

2022 카카오 블라인드 채용 - 양궁대회

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

 

 

풀이

설명

라이언이 가장 큰 점수 차이로 우승하기 위해 n발의 화살을 어떤 과녁 점수에 맞혀야 하는지를 10점부터 0점까지 순서대로 구하는 문제입니다.

 

백트래킹을 이용해 해결할 수 있습니다.

 

각 점수마다 라이언은 두 가지 선택이 가능합니다.

1. 해당 점수를 얻기 위해 화살을 사용합니다. 어피치보다 한 발 더 사용해야 합니다.
2. 해당 점수를 얻지 않습니다. 화살을 사용하지 않습니다.

 

주의해야 할 점은 다음과 같습니다.

가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지일 경우, 가장 낮은 점수를 더 많이 맞힌 경우를 구합니다.

가장 낮은 점수를 맞힌 개수가 같은 경우, 계속해서 그다음으로 낮은 점수를 더 많이 맞힌 경우를 구합니다.

 

예시 코드

function solution(n, info) {
  const MAX_SCORE = 10;

  const answer = Array(MAX_SCORE + 1).fill(0);
  let maxDiff = -1;
  let bestAnswer = [-1];

  dfs(0, n, 0);

  return maxDiff > 0 ? bestAnswer : [-1];

  function isBestAnswer(current, best) {
    for (let i = MAX_SCORE; i >= 0; i--) {
      if (current[i] > best[i]) return true;
      if (current[i] < best[i]) return false;
    }
    return false;
  }

  function dfs(index, arrowsLeft, scoreDiff) {
    if (arrowsLeft === 0 && scoreDiff < maxDiff) return;
    if (index === MAX_SCORE + 1) {
      answer[MAX_SCORE] = arrowsLeft;

      if (
        scoreDiff > maxDiff ||
        (scoreDiff === maxDiff && isBestAnswer(answer, bestAnswer))
      ) {
        maxDiff = scoreDiff;
        bestAnswer = [...answer];
      }
      answer[MAX_SCORE] = 0;

      return;
    }

    const score = MAX_SCORE - index;
    // case 1: 라이언이 index 점수를 얻기 위해 화살을 추가
    if (arrowsLeft > info[index]) {
      const usedArrows = info[index] + 1;
      answer[index] += usedArrows;
      dfs(index + 1, arrowsLeft - usedArrows, scoreDiff + score);
      answer[index] -= usedArrows;
    }

    // case 2: 라이언이 index 점수를 얻지 않음
    if (info[index] > 0) scoreDiff -= score;
    dfs(index + 1, arrowsLeft, scoreDiff);
  }
}