[programmers/js] 양궁대회

양궁대회

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

문제 설명

1. 어피치가 화살 n발을 다 쏜 후에 라이언이 화살 n발을 쏩니다.
2. 만약, k(k는 1~10사이의 자연수)점을 어피치가 a발을 맞혔고 라이언이 b발을 맞혔을 경우 더 많은 화살을 k점에 맞힌 선수가 k 점을 가져갑니다
   2-1. a = b일 경우는 어피치가 k점을 가져갑니다.
   2-2. k점을 여러 발 맞혀도 k점 보다 많은 점수를 가져가는 게 아니고 k점만 가져가는 것을 유의하세요.
   2-3. a = b = 0 인 경우, 즉, 라이언과 어피치 모두 k점에 단 하나의 화살도 맞히지 못한 경우는 어느 누구도 k점을 가져가지 않습니다.

• 예를 들어, 어피치가 10점을 2발 맞혔고 라이언도 10점을 2발 맞혔을 경우 어피치가 10점을 가져갑니다.
• 다른 예로, 어피치가 10점을 0발 맞혔고 라이언이 10점을 2발 맞혔을 경우 라이언이 10점을 가져갑니다.

3. 모든 과녁 점수에 대하여 각 선수의 최종 점수를 계산합니다.
4. 최종 점수가 더 높은 선수를 우승자로 결정합니다. 단, 최종 점수가 같을 경우 어피치를 우승자로 결정합니다.
   4-1. 라이언이 가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지 일 경우, 가장 낮은 점수를 더 많이 맞힌 경우를 return 해주세요.
   4-2. 라이언의 점수가 어피치의 점수보다 낮거나 같으면 [-1]을 return 해야 합니다.

풀이

배열의 길이가 11이고

• ryan이 점수를 가져간다.
• apeach가 점수를 가져간다.

2개의 경우만 존재하기에 완전탐색을 사용해서 문제를 풀 수 있습니다.

1. ryan, apeach 둘 중 한명이 점수를 가져가는 경우

const newArr = [...arr];
// ryan이 점수를 가져감
if (rest >= info[idx] + 1) {
  const newArr = [...arr];
  newArr[idx] = info[idx] + 1;
  dfs(idx + 1, rest - newArr[idx], apeach, ryan + (10 - idx), newArr);
}

// apeach가 점수를 가져감
const newArr2 = [...arr];
newArr2[idx] = 0;
dfs(idx + 1, rest, apeach + (info[idx] > 0 ? (10 - idx) : 0), ryan, newArr2);

2. 0점까지 점수를 확인했으면 최종 4-1을 비교해서 답을 정한다.

if (idx === 11) {
  const newArr = [...arr];
  if (rest) newArr[10] += rest;

  const diff = ryan - apeach;
  if (diff <= 0) return;

  if (diff > max) {
    max = diff
    answer = newArr;
  } else if (diff === max) {
    for (let i = 10; i >= 0; i--) {
      if (newArr[i] > answer[i]) {
        answer = newArr;
        break;
      } else if (newArr[i] < answer[i]) break;
    }
  }

  return;
}

3. 최종 코드

function solution(n, info) {
    let max = -1;
    let answer = [-1];
    
    const dfs = (idx, rest, apeach, ryan, arr) => {
        if (idx === 11) {
            const newArr = [...arr];
            if (rest) newArr[10] += rest;

            const diff = ryan - apeach;
            if (diff <= 0) return;
            
            if (diff > max) {
                max = diff
                answer = newArr;
            } else if (diff === max) {
                for (let i = 10; i >= 0; i--) {
                    if (newArr[i] > answer[i]) {
                        answer = newArr;
                        break;
                    } else if (newArr[i] < answer[i]) break;
                }
            }
            
            return;
        }
        
        const newArr = [...arr];
        // ryan이 점수를 가져감
        if (rest >= info[idx] + 1) {
            const newArr = [...arr];
            newArr[idx] = info[idx] + 1;
            dfs(idx + 1, rest - newArr[idx], apeach, ryan + (10 - idx), newArr);
        }
        
        // apeach가 점수를 가져감
        const newArr2 = [...arr];
        newArr2[idx] = 0;
        dfs(idx + 1, rest, apeach + (info[idx] > 0 ? (10 - idx) : 0), ryan, newArr2);
    }
    
    dfs(0, n, 0, 0, Array(11).fill(0));
    return answer;
}