[프로그래머스 Lv2] 양궁대회 (Python/파이썬)

1️⃣ 문제

https://school.programmers.co.kr/learn/courses/30/lessons/92342

2️⃣ 코드

import copy

def solution(n, info):
    global before, answer  
    answer = [-1]
    before = 0   # 이전에 구한 정답의 점수 차이
    
    def dfs(idx, cnt, arr):
        global answer, before
        
        # 라이언이 모든 화살을 다 쐈을 때
        if cnt == 0:
            score, peach = 0, 0   # 라이언, 어피치의 점수
            for i in range(11):
                if info[i] >= arr[i] and info[i] != 0:
                    peach += 10 - i
                elif info[i] < arr[i]:
                    score += 10 - i
            
            # 라이언의 점수가 어피치보다 크고, 이전에 구한 정답보다 점수 차이가 클 때 answer을 갱신함
            if score > peach and (score - peach) > before:
                before = score - peach
                answer = copy.deepcopy(arr)
            return
        
        if idx > 10:
            return
        
        # 백트래킹으로 화살을 쏘는 모든 경우의 수를 검사해줌 
        for i in range(cnt, -1, -1):
            arr[10-idx] += i
            dfs(idx+1, cnt-i, arr)
            arr[10-idx] -= i
    
    # 쏠 화살 점수(낮은 점수를 많이 쏜 경우가 정답이므로 0부터 검사), 남은 화살 개수, 라이언이 맞힌 과녁 점수의 개수 리스트 
    dfs(0, n, [0]*11)
    return answer

3️⃣ 풀이

어피치의 점수는 라이언이 쏜 과녁 상태에 따라 달라진다는 점을 놓쳐서 한참 헤맸다😭