문제 요약

어피치와 라이언이 각각 n발씩 화살을 쏘는데 한 점수에서 라이언이 어피치보다 더 많은 화살을 맞추어야만 그 점수를 획득할 수 있다. 단 같은 화살을 같은 점수에 맞춘 경우에는 어피치가 해당 점수를 가져간다. 라이언이 어피치를 이기면서 가장 큰 점수차를 내는 경우 중 가장 낮은 점수를 많이 맞춘 경우를 답으로 내야 한다.
상당히 조건이 많아서 힘들었던 문제였다.

문제 해결 전략

큐를 생성해 될 수 있는 경우를 모두 탐색해보는 BFS를 통해 해결의 실마리를 찾아내었다.
라이언이 화살을 10점부터 0점까지 계속 쏘는데 다 쏘기 전까지 어피치보다 화살 1개를 더 맞춘 경우와 아예 못 맞춘 경우를 큐에다 계속해서 넣어준다.
다 쏘았다면 라이언과 어피치 점수를 각각 계산해 가장 격차가 큰 것으로 답을 갱신해준다. 만약 격차가 현재 가장 큰 격차와 같다면 가장 작은 점수를 맞춘 화살 수가 더 많은 것으로 답을 갱신해준다.

코드는 아래와 같다.

from collections import deque

def compete(n, info):
    res = [-1]
    queue = deque([(0, 0, [])])
    max_gap = 0

    while queue:
        cur_idx, arrows_fired, cur_info = queue.popleft()
        if arrows_fired > n: continue

        if cur_idx < 10:
            queue.append((cur_idx + 1, arrows_fired, cur_info + [0]))
            add = info[cur_idx] + 1
            queue.append((cur_idx + 1, arrows_fired + add, cur_info + [add]))
        else:
            if arrows_fired < n:
                cur_info += [n - arrows_fired]
            else:
                cur_info += [0]
            com_a, com_r = 0, 0
            for i in range(11):
                if info[i] < cur_info[i]: com_r += 10 - i
                else:
                    if info[i] > 0:
                        com_a += 10 - i
            if com_r - com_a > max_gap:
                max_gap = com_r - com_a
                res = cur_info
            elif com_r - com_a == max_gap and com_r - com_a > 0:
                while cur_idx > -1:
                    if cur_info[cur_idx] > res[cur_idx]:
                        res = cur_info
                        break
                    elif cur_info[cur_idx] == res[cur_idx]:
                        cur_idx -= 1
                    else:
                        break

    return res

def solution(n, info):
    return compete(n, info)

결과: