문제

제한사항

풀이 방법

• 각각의 화살과녁에 어피치보다 많이 맞춘 경우와 0인 경우를 반복해서 dfs를 수행
• 만약 화살을 n개보다 많이 쏘았다면 종료
• 다 쏘았거나 0점과녁까지 다다르면 카카오와 어피치의 점수를 비교
• 카카오가 점수를 많이 받는 것이 아닌 점수차가 큰 것을 정답으로 한다.

코드

from collections import deque

def solution(n, info):
    answer = []
    answer_val=0
    dq=deque()
    dq.append((0, [0,0,0,0,0,0,0,0,0,0,0]))
    
    while dq:
        focus, arrow = dq.popleft()
        cnt=n-sum(arrow)
        #종료조건
        if cnt<0:
            continue
        if cnt==0 or focus>=10:
            arrow[10]=cnt
            lion=0
            apeach=0
            for i in range(10):
                if arrow[i]>info[i]:
                    lion+=10-i
                elif info[i]>0:
                    apeach+=10-i
            if lion>apeach:
                if answer_val<=lion-apeach:
                    answer_val=lion-apeach
                    answer=arrow.copy()
            continue
            
        arrow[focus]=info[focus]+1
        dq.append((focus+1, arrow.copy()))
        arrow[focus]=0
        dq.append((focus+1, arrow.copy()))
            
    if sum(answer)==0:
        answer.append(-1)
    return answer