문제 보기 · Level 2 · 2022 KAKAO BLIND RECRUITMENT · 정답률 40% · 푼 사람 10,939명 (2026-09-30 기준)1
문제
어피치가 화살 n발을 쏜 결과가 과녁 10점~0점별 개수로 주어진다. 라이언도 n발을 쏜다. 과녁 k점마다 더 많이 맞힌 쪽이 k점을 가져가고, 개수가 같으면 어피치가 가져간다. 둘 다 0발이면 아무도 가져가지 않는다. 라이언이 가장 큰 점수 차로 이기는 방법을 10점~0점 순 배열로 돌려준다. 이길 수 없으면 [−1]을 돌려준다.
- 1 ≤ n ≤ 10
- 점수 차가 최대인 방법이 여럿이면 가장 낮은 점수를 더 많이 맞힌 쪽을, 그것도 같으면 그다음 낮은 점수를 더 많이 맞힌 쪽을 고른다
풀이
막히면 한 단계씩 펼친다2.
필요한 개념
재귀와 백트래킹: 과녁마다 “이긴다 / 포기한다”를 하나씩 정하며 모든 경우를 돈다.
1단계 · 작은 예로 손으로 풀기
n = 2, 어피치는 10점에 1발, 9점에 1발을 맞혔다.
| 라이언의 선택 | 라이언 점수 | 어피치 점수 | 결과 |
|---|---|---|---|
| 10점에 2발 | 10 | 9 | 1점 차로 이김 |
| 9점에 2발 | 9 | 10 | 짐 |
| 8점 1발, 7점 1발 | 15 | 19 | 짐 |
| 10점 1발, 9점 1발 | 0 | 19 | 짐 (같으면 어피치) |
이기는 방법은 10점에 2발뿐이다. 답은 [2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]이다.
한 과녁을 이기려면 어피치보다 딱 한 발 더면 된다. 더 쏴도 점수는 같다. 그보다 적게 쏘면 못 이긴다.
2단계 · 가장 단순한 방법과 그 속도
화살 n발을 과녁 11칸에 나누는 모든 경우를 만든다. n = 10이면 C(20, 10) = 184,756가지다. 같은 화살 n발을 11칸에 나누는 수는 중복조합 C(11 + n − 1, n)이기 때문이다(중복을 허용하는 셈). 경우마다 11칸을 비교해도 200만 번 정도라 사실 이것도 된다.
하지만 1단계의 관찰을 쓰면 훨씬 적다. 과녁마다 선택은 두 가지뿐이다. 이기려면 (어피치 + 1)발, 포기하면 0발. 1점~10점 10칸이라 2¹⁰ = 1,024가지이고, 남은 화살은 모두 0점에 둔다. 1,024는 곱의 법칙으로 센 최대치이고, 화살이 모자라 “이긴다”를 고를 수 없는 칸이 생기면 실제 경우는 더 적다.
3단계 · 핵심 아이디어
- 두 선택만 보는 이유: 이길 칸에 (어피치 + 1)발보다 더 쏘거나, 포기할 칸에 몇 발 쏴도 점수 차는 그대로다. 그 남는 화살을 0점에 두면 점수 차는 같으면서 “낮은 점수를 더 많이”라는 동점 규칙에서 유리해진다. 그래서 최선의 답은 늘 이 모양 안에 있다.
- 재귀: 10점 칸(번호 0)부터 1점 칸(번호 9)까지, 화살이 남으면 “이긴다”를, 늘 “포기한다”를 시도한다. 마지막에 남은 화살을 0점 칸(번호 10)에 둔다.
- 점수 계산: k번 칸(10 − k점)마다 라이언이 더 많으면 라이언, 아니고 어피치가 1발 이상이면 어피치가 점수를 가진다.
- 동점 규칙: 점수 차가 같으면 배열을 뒤집어(0점 칸부터) 크기를 비교해 큰 쪽을 고른다. 파이썬 리스트 비교가 앞 칸부터 하므로
a[::-1] > b[::-1]이 “낮은 점수를 더 많이”다.
4단계 · 코드 흐름
- 최고 차이 0, 최고 답 [−1]로 시작한다.
- 재귀 go(칸 번호, 남은 화살):
- 칸 번호가 10(0점 칸)이면 남은 화살을 두고 점수 차를 계산한다. 더 크거나, 같고 0보다 크면서 동점 규칙에서 이기면 답을 바꾼다.
- 아니면: 남은 화살로 이길 수 있으면 (어피치 + 1)발을 두고 다음 칸으로. 되돌린 뒤 0발로 다음 칸으로.
- 최고 답을 돌려준다.
5단계 · 파이썬 코드
def solution(n, info):
best_diff, best = 0, [-1]
ryan = [0] * 11 # ryan[k]: 10 - k점에 쏜 화살
def go(i, left):
nonlocal best_diff, best
if i == 10: # 0점 칸: 남은 화살을 모두 둔다
ryan[10] = left
r = a = 0
for k in range(10):
if ryan[k] > info[k]:
r += 10 - k
elif info[k] > 0:
a += 10 - k
diff = r - a
if diff > best_diff or (diff == best_diff and diff > 0 and ryan[::-1] > best[::-1]):
best_diff, best = diff, ryan[:]
ryan[10] = 0
return
need = info[i] + 1
if need <= left: # 이 점수를 이긴다
ryan[i] = need
go(i + 1, left - need)
ryan[i] = 0 # 되돌리기
go(i + 1, left) # 이 점수는 포기한다
go(0, n)
return best
nonlocal best_diff, best: 안쪽 함수에서 바깥 함수의 변수를 바꾸겠다는 선언이다. 없으면 안에서 새 변수가 생겨 바깥 값이 바뀌지 않는다.ryan[:]: 지금 배열을 복사해 저장한다.ryan은 계속 고쳐 쓰는 리스트이기 때문이다.ryan[::-1] > best[::-1]: 0점 칸부터 비교해 낮은 점수를 더 많이 맞힌 쪽이 크다.
6단계 · 실행 추적
n = 5, 어피치 [2, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0] (10점 2발, 9·8·7점 각 1발). 어피치가 가진 점수는 34점이다.
| 라이언이 이기는 칸 | 쓴 화살 | 라이언 | 어피치 | 차 |
|---|---|---|---|---|
| 9, 8 (각 2발), 6 (1발) | 5 | 23 | 17 | 6 |
| 10 (3발), 9 (2발) | 5 | 19 | 15 | 4 |
| 9 (2발), 6, 5, 4 (각 1발) | 5 | 24 | 25 | −1 |
1,024가지 중 차가 가장 큰 것은 6이고, 답은 [0, 2, 2, 0, 1, 0, 0, 0, 0, 0, 0]이다.
7단계 · 복잡도와 흔한 실수
2¹⁰가지마다 11칸을 계산하니 약 1만 번이다.
- 개수가 같을 때 라이언이 가져간다고 본다. 같으면 어피치다.
- 둘 다 0발인 칸을 어피치 점수로 센다. 아무도 가져가지 않는다.
- 남은 화살을 쓰지 않아 합이 n이 아닌 배열을 돌려준다.
- 동점 규칙을 “높은 점수를 더 많이”로 거꾸로 비교한다.
- 비겼을 때(차 0)를 이긴 것으로 친다.