프로그래머스 LEVEL 2(양궁대회)

사용 언어 : javascript
해결 날짜 : 2023-01-01
해결 방법 :
- dfs를 통해 문제 해결
- dfs의 종료 조건은 남은 화살 갯수(leftArrowCount)가 0이 될 때
  - 현재까지 저장된 두 선수의 점수 차이(scoreDiffer)과 현재 새로 구한 두 선수의 점수 차이(currentScoreDiffer) 중 큰 값 저장
- 화살을 쏠 때 작은 점수의 화살부터 쏨
  - 이 때 남은 화살 개수가 현재 인덱스의 어피치가 쏜 화살 개수보다 많이 남아있다면
    - 현재 인덱스의 어피치가 쏜 화살보다 한 개 더 쏘고 dfs
  - 같거나 적다면 가장 작은 점수의 화살로 전부 쏘고 남은 화살 개수 0으로 dfs
- 화살을 다 쏘고 나서도 화살이 남아 있다면 가장 적은 점수의 화살로 전부 쏘고 남은 화살 개수 0으로 dfs
회고 :
- dfs를 다 돌고도 남은 화살 갯수(leftArrowCount)가 있을 경우를 생각하는데 오래 걸렸다.

코드

function solution(n, info) {
  let answer = [];
  const initialArray = Array.from({ length: 11 }, () => 0);
  const initialIndex = 0;
  let scoreDiffer = 0;

  const calcScoreDiffer = (array) => {
    return info.reduce((acc, cur, i) => {
      const idx = 10 - i;
      if (cur === 0 && array[i] === 0) return acc;
      else if (cur < array[i]) return acc + idx;
      else return acc - idx;
    }, 0);
  };

  const dfs = (leftArrowCount, array, index = -1) => {
    if (leftArrowCount === 0) {
      const currentScoreDiffer = calcScoreDiffer(array);
      if (currentScoreDiffer > scoreDiffer) {
        scoreDiffer = currentScoreDiffer;
        answer = [...array];
      }
      return;
    }

    for (let i = index; i <= 10; i++) {
      const idx = 10 - i;
      const arr = [...array];

      if (leftArrowCount > info[idx]) {
        arr[idx] = info[idx] + 1;
        dfs(leftArrowCount - arr[idx], arr, i + 1);
      } else {
        arr[10] += leftArrowCount;
        dfs(0, arr, i + 1);
      }
    }

    const arr = [...array];
    arr[10] += leftArrowCount;
    dfs(0, arr);
  };

  dfs(n, initialArray, initialIndex);

  return answer.length ? answer : [-1];
}

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges