🧩 문제 해석 및 해결 전략
이 문제는 라이언과 어피치의 양궁 점수 계산 방식에 따라 라이언이 가장 큰 점수 차이로 이길 수 있는 경우의 화살 분배를 찾는 것이 목표입니다. 단순히 점수 차이가 큰 경우뿐만 아니라, 점수 차이가 같을 경우 더 낮은 점수에 많은 화살을 사용한 경우를 우선해야 한다는 조건이 있습니다.
🎯 문제의 핵심 규칙
- 과녁 점수: 10점부터 0점까지 11개의 점수 구역이 있습니다.
- 승리 조건: 각 점수 구역에서 더 많은 화살을 쏜 선수가 해당 점수를 가져갑니다. 화살 수가 같으면 어피치가 점수를 가져갑니다.
- 라이언의 목표: 어피치와의 점수 차이를 최대로 만들면서 이기는 경우를 찾아야 합니다.
- 동점 시 우선순위: 점수 차이가 같은 경우, 낮은 점수(0점에 가까운 점수)에 더 많은 화살을 쏜 기록을 우선합니다.
🤔 DFS를 사용하는 이유
각 점수 구역(10점 ~ 0점)에 대해 라이언이 취할 수 있는 선택은 크게 두 가지입니다:
- 해당 점수를 포기하고 어피치에게 점수를 내주는 경우: 라이언은 그 점수 구역에 화살을 쏘지 않습니다.
- 해당 점수를 획득하는 경우: 라이언은 어피치가 쏜 화살 수보다 1발 더 많이 쏴서 점수를 획득합니다. 단, 남은 화살이 충분해야 합니다.
이처럼 각 점수 구역마다 선택지가 있고, 이 선택이 남은 화살 수와 최종 점수에 영향을 미치므로, 모든 가능한 경우의 수를 탐색해야 합니다. DFS(깊이 우선 탐색)는 이러한 모든 조합을 체계적으로 탐색하기에 적합한 완전 탐색 기법입니다.
🧠 해결 전략 요약 (DFS)
주어진 화살 n발을 11개의 점수 구역에 어떻게 분배할지 결정하는 DFS 함수를 설계합니다.
dfs(index, left, lion, apeach, records)
index: 현재 탐색 중인 점수 구역 (0: 10점, ..., 10: 0점)left: 라이언에게 남은 화살 수lionScore,apeachScore: 현재까지 계산된 라이언과 어피치의 총점lionArrows: 라이언이 각 점수 구역에 쏜 화살 수를 기록하는 배열 (길이 11)
종료 조건 (index === 11)
- 모든 점수 구역에 대한 화살 분배가 완료되었을 때
- 남은 화살이 있다면, 가장 낮은 점수인 0점(
records[10])에 몰아줍니다. - 라이언이 어피치를 이겼는지 확인하고, 점수 차이가
bestDiff보다 크면bestRecord를 갱신합니다. - 점수 차이가
bestDiff와 같으면, 0점부터 역순으로 비교하여 더 많은 화살을 쏜 기록을bestRecord로 갱신합니다.
재귀 호출
-
라이언이 해당 점수를 포기하는 경우:
info[index]값이 0보다 크다면 어피치가(10 - index)점수를 가져갑니다.left와records는 그대로 다음index로 넘어갑니다. -
라이언이 해당 점수를 획득하는 경우: 어피치가 쏜 화살 수(
info[index])보다 1발 더 많은 화살(info[index] + 1)이 필요합니다. 남은 화살(left)이 충분하다면, 라이언은 (10 - index) 점수를 가져가고,left는need만큼 줄어들며,records[index]에need를 기록하고 다음index로 넘어갑니다.
❓ 단계별 풀이과정
1. 초기 변수 선언
let bestDiff = -1; // 라이언과 어피치의 점수 차 중 가장 큰 점수 차이
let bestRecord = [-1]; // 그 때의 라이언 화살 분배 기록. 초기에는 이길 수 없는 상태를 나타냄2. DFS 함수 개요
function dfs(index, left, lion, apeach, records) {
// ...
}index: 현재 처리할 과녁 점수 인덱스 (0~10은 10점~0점)left: 라이언이 남은 화살 수lion,apeach: 현재까지 각각의 점수 합records: 라이언이 각 점수에 쏜 화살 수를 저장하는 배열 (길이 11)
🔸 3. 종료 조건 (index === 11)
if (index === 11) {
const copied = [...records]; // 현재까지의 라이언 화살 기록 복사
if (left > 0) copied[10] += left; // 남은 화살은 0점 과녁에 모두 몰아줌
const diff = lion - apeach; // 라이언과 어피치의 점수 차이 계산
// 라이언이 이긴 경우에만 기록 갱신 시도
if (diff > 0) {
if (diff > bestDiff) { // 현재 점수 차이가 기존 최고 점수 차이보다 크면 무조건 갱신
bestDiff = diff;
bestRecord = copied;
} else if (diff === bestDiff) { // 점수 차이가 같으면 낮은 점수부터 비교 (문제 조건)
for (let i = 10; i >= 0; i--) { // 0점(인덱스 10)부터 역순으로 비교
if (copied[i] > bestRecord[i]) { // 현재 기록이 기존 최고 기록보다 해당 점수에 화살을 더 많이 쏜 경우
bestRecord = copied; // 갱신
break; // 더 이상 비교할 필요 없음
} else if (copied[i] < bestRecord[i]) { // 현재 기록이 기존 최고 기록보다 해당 점수에 화살을 덜 쏜 경우
break; // 갱신하지 않고 다음 경로 탐색
}
}
}
}
return; // 재귀 호출 종료
}
- 모든 점수 탐색이 끝났을 때 동작함
- 남은 화살이 있다면 0점에 추가함
lion > apeach인 경우에만 bestRecord 갱신- 점수 차가 같은 경우에는 낮은 점수부터 비교하여 더 많은 화살을 쏜 경우 우선
🔸 4. 쏘지 않는 경우 (어피치가 점수 가져감)
// 1. 라이언이 현재 index의 점수(10-index점)를 포기하는 경우
// 이 경우, 어피치가 해당 점수에 화살을 쏜 기록(info[index])이 있다면 어피치가 점수를 가져간다.
dfs(
index + 1, // 다음 점수 구역으로 이동
left, // 남은 화살 수는 그대로
lion, // 라이언 점수 그대로
info[index] > 0 ? apeach + (10 - index) : apeach, // 어피치가 화살을 쐈으면 점수를 획득, 아니면 그대로
records // 라이언의 화살 기록은 이 점수 구역에 대해 변화 없음
);
🔸 5. 쏘는 경우 (라이언이 점수 가져감)
// 2. 라이언이 현재 index의 점수(10-index점)를 획득하는 경우
// 라이언은 어피치보다 1발 더 많이 쏴야 한다.
const need = info[index] + 1; // 이 점수를 획득하기 위해 필요한 화살 수
// 라이언에게 필요한 화살 수가 충분히 남아있을 때만 시도
if (left >= need) {
const copied = [...records]; // 현재까지의 라이언 화살 기록을 복사 (새로운 경로 생성)
copied[index] = need; // 현재 점수 구역에 필요한 만큼 화살 기록
dfs(
index + 1, // 다음 점수 구역으로 이동
left - need, // 남은 화살 수 감소
lion + (10 - index), // 라이언 점수 획득
apeach, // 어피치 점수는 그대로
copied // 업데이트된 라이언 화살 기록 전달
);
}
✅ 최종 코드
function solution(n, info) {
let bestDiff = -1; // 라이언이 이길 수 있는 경우 중 가장 큰 점수 차이
let bestRecord = [-1]; // 그 때의 라이언 화살 분배 기록. 초기에는 이길 수 없는 상태를 나타냄
// DFS 함수 정의
// index: 현재 처리할 과녁 점수 인덱스 (0: 10점, 1: 9점, ..., 10: 0점)
// left: 라이언이 남은 화살 수
// lion: 현재까지 라이언의 총점
// apeach: 현재까지 어피치의 총점
// records: 라이언이 각 점수에 쏜 화살 수를 저장하는 배열 (현재 경로)
function dfs(index, left, lion, apeach, records) {
// 모든 점수 구역을 탐색 완료했을 때 (종료 조건)
if (index === 11) {
const copied = [...records]; // 현재까지의 라이언 화살 기록을 복사
if (left > 0) copied[10] += left; // 남은 화살은 0점 과녁에 모두 몰아줌
const diff = lion - apeach; // 라이언과 어피치의 점수 차이 계산
// 라이언이 이긴 경우에만 기록 갱신 시도
if (diff > 0) {
if (diff > bestDiff) { // 현재 점수 차이가 기존 최고 점수 차이보다 크면 무조건 갱신
bestDiff = diff;
bestRecord = copied;
} else if (diff === bestDiff) { // 점수 차이가 같으면 낮은 점수부터 비교 (문제 조건)
// 0점(인덱스 10)부터 역순으로 비교하여 더 낮은 점수에 더 많은 화살을 쏜 경우를 선택
for (let i = 10; i >= 0; i--) {
if (copied[i] > bestRecord[i]) { // 현재 기록이 기존 최고 기록보다 해당 점수에 화살을 더 많이 쏜 경우
bestRecord = copied; // 갱신
break; // 갱신했으므로 더 이상 비교할 필요 없음
} else if (copied[i] < bestRecord[i]) { // 현재 기록이 기존 최고 기록보다 해당 점수에 화살을 덜 쏜 경우
break; // 갱신하지 않고 다음 경로 탐색
}
}
}
}
return; // 재귀 호출 종료
}
// 1. 라이언이 현재 index의 점수(10-index점)를 포기하는 경우
// 이 경우, 어피치가 해당 점수에 화살을 쏜 기록(info[index])이 있다면 어피치가 점수를 가져간다.
dfs(
index + 1, // 다음 점수 구역으로 이동
left, // 남은 화살 수는 그대로
lion, // 라이언 점수 그대로
info[index] > 0 ? apeach + (10 - index) : apeach, // 어피치가 화살을 쐈으면 점수를 획득, 아니면 그대로
records // 라이언의 화살 기록은 이 점수 구역에 대해 변화 없음
);
// 2. 라이언이 현재 index의 점수(10-index점)를 획득하는 경우
// 라이언은 어피치보다 1발 더 많이 쏴야 한다.
const need = info[index] + 1; // 이 점수를 획득하기 위해 필요한 화살 수
// 라이언에게 필요한 화살 수가 충분히 남아있을 때만 시도
if (left >= need) {
const copied = [...records]; // 현재까지의 라이언 화살 기록을 복사 (새로운 경로 생성)
copied[index] = need; // 현재 점수 구역에 필요한 만큼 화살 기록
dfs(
index + 1, // 다음 점수 구역으로 이동
left - need, // 남은 화살 수 감소
lion + (10 - index), // 라이언 점수 획득
apeach, // 어피치 점수는 그대로
copied // 업데이트된 라이언 화살 기록 전달
);
}
}
// DFS 탐색 시작
// 초기 호출: 0점(10점 과녁), n발의 화살, 라이언/어피치 점수 0, 라이언 화살 기록은 모두 0으로 초기화된 배열
dfs(0, n, 0, 0, Array(11).fill(0));
return bestRecord; // 최종적으로 찾은 최고 기록 반환
}