양궁대회

import copy

⭐️
answer = []
maxDiff = -1

def calc(ryan, apeach):
    sumL, sumA = 0, 0
    for idx, (l, a) in enumerate(zip(ryan, apeach)):
        if l > a:
            sumL += (10-idx)
        elif l == a == 0:
            continue
        else:
            sumA += (10-idx)
    return sumL - sumA


def dfs(apeach, ryan, n, idx):
    global maxDiff, answer
    
    # Termination 조건
    if idx == 11:
        # 화살이 남았으면 마지막 0점에 몰아주기
        if n > 0:
            ryan[10] = n
        scoreDiff = calc(ryan, apeach)
        if scoreDiff <= 0: # 라이언이 우승할 방법X
            return
        temp = copy.deepcopy(ryan)
        if scoreDiff > maxDiff:
            maxDiff = scoreDiff
            answer = [temp]
        elif scoreDiff == maxDiff:
            answer.append(temp)
        return
    
    # 점수 따는 경우
    if apeach[idx] < n:
        ryan.append(apeach[idx]+1)
        dfs(apeach, ryan, n - (apeach[idx]+1), idx+1)
        ryan.pop()
    
    # 점수 못따는 경우
    ryan.append(0)
    dfs(apeach, ryan, n, idx+1)
    ryan.pop()
    

def solution(n, info):
    global answer
    
    # 완전 탐색 - 2^11
    # 아예 0개를 쏘거나, 어피치+1 개를 쏘거나
    dfs(info, [], n, 0)
    
    # 정답형식 처리
    if len(answer) == 0:
        return [-1]
    
    # 가장 낮은 점수 개수가 많은 경우 선택
    answer.sort(key=lambda x: x[::-1], reverse=True)
    
    return answer[0]

처음에는 아이디어를 생각하지 못했다.

아예 화살 0개를 쏘거나(점수 포기), 어피치+1 개를 쏘거나(점수 쟁취)

또, 구현도 만만치 않았다.
고민한 결과, DFS 백트래킹이 따져야 할 경우의 수도 그렇고 구현하기에 가장 수월해 보였다.

중간 중간에 세밀한 조건 처리도 중요했다. Apeach와 Ryan이 모두 0점일 경우 점수 없음, answer에 후보 답을 넣을 때 deepcopy로 넣어야 한다는 점 등.

프로그래머스 연습문제, https://school.programmers.co.kr/learn/challenges