2022 카카오 코딩테스트 lv.2 양궁대회 파이썬

def dfs(n, info, k, apeach, lion, temp):
    if n == 0:
        global max_val, answer
        if lion - apeach > max_val:
            max_val = lion - apeach
            answer = temp[:]

        elif lion - apeach == max_val and max_val != 0:
            for i in range(10, -1, -1):
                if temp[i] > answer[i]:
                    answer = temp[:]
                    break
                elif temp[i] < answer[i]:
                    break
        return

    for i in range(k, 11):
        if n > info[i]:
            temp[i] = info[i] + 1
            if info[i] > 0:
                dfs(n - temp[i], info, i + 1, apeach - (10 - i), lion + (10 - i), temp)
            else:
                dfs(n - temp[i], info, i + 1, apeach, lion + (10 - i), temp)
            temp[i] = 0
        else:
            if i == 10:
                temp[i] = n
                dfs(0, info, i + 1, apeach, lion, temp)
                temp[i] = 0
            else:
                dfs(n, info, i + 1, apeach, lion, temp)


def solution(n, info):
    global max_val, answer
    apeach = 0; answer = [0] * 11; max_val = 0
    for i in range(11):
        if info[i] > 0:
            apeach += 10 - i
    dfs(n, info, 0, apeach, 0, [0] * 11)
    if answer == [0] * 11:
        answer = [-1]
    return answer

dfs로 풀었습니다.

k점 과녁에 어피치와 같거나, 더 적게 맞히면 점수를 얻을 수 없습니다.

따라서 어피치보다 한발 더 쏘거나, 아예 맞히질 말아서 화살을 아껴야 합니다.

 

남은 화살의 개수가 0이 되면 라이언과 어피치의 점수 차이를 구합니다. 이때 기존값보다 점수 차이가 크다면, 새롭게 값을 갱신해줍니다. 만약 기존값과 같다면, 가장 낮은 점수를 더 많이 맞힌 경우로 갱신합니다.