문제
풀이
- 양궁게임에 몰입해서 게임에서 있을 수 있는 케이스를 파악 후 의식의 흐름대로 풀면 쉽게 풀 수 있는 문제였다.
- n의 최대값이 10으로 재귀를 통해 모든 경우의 수를 구해서 그 중 두 플레이어의 점수 차가 가장 큰 경우를 구하면 된다. 이 때 주의할 점은 2가지가 있었다.
- 라이언이 큰 점수 차이로 우승할 수 있는 방법이 여러 가지 일 경우, 가장 낮은 점수를 더 많이 맞힌 경우를 선택한다. 이 문제는 재귀를 수행할 때 낮은 점수부터 수행하면 해결된다.
- 화살의 개수가 남는 경우가 존재한다. 이 문제는 남은 화살을 모두 0점에 더하면 해결할 수 있다.
- 재귀를 수행할 때 정상적인 경우 외에 도중에 화살을 모두 사용하는 경우와 화살은 있지만 개수가 부족한 경우 등을 고려한다.
소스 코드
function solution(n, info) {
const result = Array.from({ length: 11 }, () => 0);
let answer = [-1];
let diff = 0;
function dfs(score, arrow, r_total, a_total) {
if (score === 11) {
// 라이언이 이기는 케이스는 해당값이 반드시 양수
const temp = r_total - a_total
if (temp <= diff) return;
diff = temp;
result[10] += arrow;
answer = [...result];
result[10] -= arrow;
return;
}
if (arrow === 0) {
if (info[10 - score] === 0) return dfs(score + 1, arrow, r_total, a_total);
return dfs(score + 1, arrow, r_total, a_total + score);
}
const target = info[10 - score] + 1;
if (arrow >= target) {
result[10 - score] = target;
dfs(score + 1, arrow - target, r_total + score, a_total);
}
result[10 - score] = 0;
if (info[10 - score] === 0) dfs(score + 1, arrow, r_total, a_total);
else dfs(score + 1, arrow, r_total, a_total + score);
}
dfs(0, n, 0, 0)
return answer;
}