프로그래머스 - 양궁대회 (L2)

 1def solution(n, info):
 2    # 각각 몇 번 맞춰야 점수를 얻는지 저장하였다
 3    goal_list = [i+1 for i in info]
 4
 5    cases = []
 6
 7    def dfs(score, cnt, case):
 8        # 몇 번째 점수인지 나타낸다 (0:10점, 1:9점, ...)
 9        length = len(case)
10        if length == 11:
11            # 화살 개수가 남았다면 0점에 채워준다
12            if cnt != n:
13                case[-1] += n-cnt
14            cases.append((score, case))
15            return
16        # 현재 단계에서 몇 점 맞아야 점수를 따는지를 나타낸다
17        goal = goal_list[length]
18
19        # 점수를 따는 경우
20        if cnt + goal <= n:
21            # 딴 점수를 더해준다
22            dfs(score+(10-length), cnt+goal, case+[goal])
23        # 상대가 점수를 따는 경우
24        if goal != 1:
25            # 상대가 딴 점수를 빼준다
26            dfs(score-(10-length), cnt, case+[0])
27        # 아무도 못 맞추는 경우
28        else:
29            dfs(score, cnt, case+[0])
30            
31    dfs(0, 0, [])
32    # 점수가 같다면, 낮은 점수를 더 많이 맞춘 경우를 반환하기 위해 역순으로 정렬하였다
33    cases.sort(key= lambda x: (x[0], x[1][::-1]))
34
35    if cases[-1][0] > 0:
36        return cases[-1][1]
37    # 가장 우선순위가 높은 case의 점수가 음수인 경우, 무조건 지는 경우로 간주한다    
38    return [-1]