문제

https://school.programmers.co.kr/learn/courses/30/lessons/92342?language=cpp

카카오베 양궁대회가 열렸다.
어피치가 화살 n발을 쐈는데 라이언이 과녁에 어느부분에 화살을 쏴야 이길수 있는지 구하자.
만약 어떻게 해도 무승부거나 지는경우 [-1]을 리턴한다.

정답코드(c++)

#include <algorithm>
#include <numeric>
#include <vector>
using namespace std;

// 처음 파라메터로 들어오는 info
vector<int> globalInfo;
// 탐색하며 계속 변경되는 라이언이 화살 쏜 정보
vector<int> globalResult;
// 최종 결과
vector<vector<int>> result;
// 점수차 최대치
int maxDifference;

int getApeachScore() {
  int score = 0;
  for (int i = 0; i < 11; i++) {
    if (globalInfo[i] != 0 && globalResult[i] == 0) {
      score += 10 - i;
    }
  }
  return score;
}

void dfs(int now, int leftArrow, int nowScore) {
  // 끝까지 탐색했다면?
  if (now == 11) {
    int lion = nowScore;
    int apeach = getApeachScore();
    int difference = lion - apeach;
    vector<int> tmpResult = globalResult;

    // 남은화살 처리
    if (leftArrow > 0) {
      tmpResult[10] = leftArrow;
    }
    // 점수차가 제일 많이나는거 초과라면 그냥 넣어줌
    if (difference > maxDifference) {
      maxDifference = difference;
      result = vector(1, tmpResult);
    }
    // 만약 두개가 같다면 뒤에 더 많이 맞춘거 넣어줌
    else if (difference == maxDifference) {
      result.push_back(tmpResult);
    }
  }

  for (int i = now; i < 11; i++) {
    int score = 10 - i;
    // 라이언이 과녁을 쏠 수 있을 경우
    if (globalInfo[i] < leftArrow) {
      // int tmp = globalResult[i];
      globalResult[i] = globalInfo[i] + 1;
      dfs(i + 1, leftArrow - globalInfo[i] - 1, nowScore + score);
      globalResult[i] = 0;
    }
    // 쏠수 없는경우
    else {
      dfs(i + 1, leftArrow, nowScore);
    }
  }
}
vector<int> solution(int n, vector<int> info) {
  globalInfo = info;
  globalResult = vector(11, 0);
  result.clear();
  maxDifference = 0;

  dfs(0, n, 0);

  sort(result.rbegin(), result.rend(), [](auto a, auto b) {
    for (int i = 10; i >= 0; i--) {
      if (a[i] != b[i]) {
        return (a[i] < b[i]);
      }
    }
    return false;
  });
  return maxDifference == 0 ? vector(1, -1) : result[0];
}

정답코드 (js)

const solution = (n, info) => {
  let sameResult = [];
  let result = Array(11).fill(0);
  let maxDifference = 0;

  const getApeachScore = () => {
    let score = 0;
    for (let i = 0; i < 11; i++) {
      if (info[i] !== 0 && result[i] === 0) score += 10 - i;
    }
    return score;
  };
  const dfs = (now, leftArrow, nowScore) => {
    if (now === 11) {
      let difference = nowScore - getApeachScore();
      let tmpResult = [...result];

      if (leftArrow > 0) tmpResult[10] = leftArrow;
      if (difference > maxDifference) {
        maxDifference = difference;
        sameResult = [[...tmpResult]];
      } else if (difference === maxDifference) {
        sameResult.push(tmpResult);
      }
    }
    for (let i = now; i < 11; i++) {
      const score = 10 - i;
      if (info[i] < leftArrow) {
        result[i] = info[i] + 1;
        dfs(i + 1, leftArrow - info[i] - 1, nowScore + score);
        result[i] = 0;
      } else {
        dfs(i + 1, leftArrow, nowScore);
      }
    }
  };

  dfs(0, n, 0);
 
  sameResult.sort((a, b) => {
    for (let i = 10; i >= 0; i--) {
      if (a[i] !== b[i]) return b[i] - i[i];
    }
  });
  return maxDifference === 0 ? [-1] : sameResult[0];
};

문제 접근

문제의 핵심

이 문제를 일반화하면 핵심은 아래 세가지로 추려진다.

1. 점수차가 가장 많이나는 경우를 구한다.
2. 점수차가 많이나는경우가 여러개라면 그중 가장 낮은점수를 더 많이 맞춘경우를 리턴한다.
3. 우승할 방법이 없는경우 [-1]을 리턴한다.

자세한 설명

이 문제를 보고 해석해보면 정답이 단 한개가 아니라 여러개일수도 있고,
여러개라면 그중 가장 낮은점수를 더 많이 맞춘경우를 출력해야한다.
여기서 dfs, 백트래킹을 이용한 완전탐색을 바로 떠올렸다.

1. 탐색방법

완전탐색 방법은 우선 dfs 함수 안에서 for문을 0 ~ 10까지 돈다
라이언이 해당 (10-i)점의 과녁을 쏠 수 있다면 쏘면서 점수와 남은화살에 대한 정보와 함께 dfs를 호출하고,
쏠수 없다면 점수와 남은화살에 대한 정보는 변함없이 dfs문을 호출한다.

---

2. 리프노드에 도달후 처리

dfs로 탐색을 진행하며 어피치의 점수는 구하지 않았기 때문에 어피치의 점수부터 구해준다.
방법은 간단한데 info[i] != 0 && result[i] == 0 일경우
해당 과녁의 점수를 더한 총계가 어피치의 점수다.

2-1. 남은화살이 있을경우

남은 화살이 1개 이상이라면 이를 모두 0점 과녁에 추가한다.
이유는 문제에서 아래와같은 설명이 있었기 때문이다.

라이언이 가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지 일 경우,
가장 낮은 점수를 더 많이 맞힌 경우를 return 해주세요.

탐색을 마쳤는데도 화살이 남아있다면 그건 어디에 쏴도 점수를 얻을 수 없는 경우이다.
이 경우 가장 낮은 점수를 더 많이 맞힌 경우는 0점에 모두 맞히는 경우밖에 없다.
그렇기 때문에 남은 화살을 모두 0점 과녁에 추가한다.

2-2. 두 선수의 점수차가 최대와 같다면

점수차의 최대치는 처음에는 0으로 초기화 되어있다.
그 후에 라이언 점수 - 어피치 점수가 이전 최대치와 같다면
결과에 현재 라이언이 맞힌 과녁에대한 정보를 넣어준다.

1. 결과.push( 현재 라이언이 맞힌 과녁 )

2-3. 두 선수의 점수차가 최대치보다 크다면

현재 점수차가 최대치보다 크다면 이전 정보들은 필요가 없게된다.
그래서 이전에 결과에 넣었던 정보들은 지우고 새롭게 현재 라이언이 맞힌 과녁의 정보를 넣는다.
그 후 점수차 최대치를 현재 점수차로 갱신한다.

1. 결과 = list(현재 라이언이 맞힌 과녁)
2. 점수차 최대치 = 라이언 점수 - 어피치 점수

---

3. 모든 노드의 탐색을 마친후

탐색을 마치면 결과에는 최대치가 가장 크게 라이언이 이기는 방법들이 들어있다.
근데 이기는 방법이 0개라면 [-1]을 리턴해준다.

만약 이기는 방법이 여러개 존재한다면 정렬을 해줘야한다.
정렬 방법은 각각 방법들의 원소를 뒤에서 부터 보며 더 큰 값부터 내림차순으로 정렬해줘야 한다.

c++의 경우 아래와 같이 sort를 사용하면 된다.
그럼 2차원벡터의 행을 뒷부분의 원소를 기준으로 내림차순으로 정렬해준다.

sort(result.rbegin(), result.rend(), [](auto a, auto b) {
  for (int i = 10; i >= 0; i--) {
    if (a[i] != b[i]) {
      if (a[i] < b[i])
        return true;
      else
        return false;
    }
  }
  return false;
 });

또다른 방법으로는 reverse()를 사용해 정렬후 다시 reverse()를 사용하는 방법이 있다.
이런식으로 정렬하면 된다.

for (auto &row : result) {
  reverse(row.begin(), row.end());
}
sort(result.rbegin(), result.rend());
for (auto &row : result) {
  reverse(row.begin(), row.end());
}

js의 경우 array의 sort 메서드를 사용하면 된다.

sameResult.sort((a, b) => {
  for (let i = 10; i >= 0; i--) {
    if (a[i] !== b[i]) return b[i] - i[i];
  }
});

이렇게 정렬후 result[0]이 결과가 된다.