[Python] 프로그래머스 Lv2 - 양궁대회 (2022 KAKAO BLIND RECRUITMENT)

🔗 문제링크

코딩테스트 연습 - 양궁대회

📂 분류

백트래킹 완전탐색

💡 풀이

친구가 파이썬으로 알고리즘 문제 푸는 것을 보고 파이썬이 편해 보이길래 파이썬으로 풀어보았다.

 

이 문제는 n의 크기가 10 이하 이므로 백트래킹 + 완전탐색으로 해결할 수 있는 문제이다.

 

접근 방식

• 라이언이 점수를 획득할지의 여부를 체크하면서 재귀 함수를 진행한다.
• 라이언의 최대 점수를 경신하면서 answer에 과녁 점수를 넣어준다.
• 가장 낮은 점수를 더 많인 경우를 반환해야 하기 때문에 낮은 점수를 기준으로 정렬을 해준다.

💻 코드

import copy

maxScoreDiff = 0
answer = []


def calc_score_diff(ryans, apeachs):
    ryan = 0
    apeach = 0

    for i in range(10):
        if (ryans[i], apeachs[i]) == (0, 0):
            continue
        if ryans[i] > apeachs[i]:
            ryan += 10 - i
        else:
            apeach += 10 - i

    return ryan - apeach


def dfs(info, shots, n, i):
    global maxScoreDiff, answer
    if i == 11:
        score_diff = calc_score_diff(shots, info)
        if score_diff <= 0:
            return
        res = copy.deepcopy(shots)
        if maxScoreDiff < score_diff:
            maxScoreDiff = score_diff
            answer = [res]
            return
        if maxScoreDiff == score_diff:
            answer.append(res)
        return

    if info[i] < n:
        shots.append(info[i] + 1)
        dfs(info, shots, n - info[i] - 1, i + 1)
        shots.pop()

    shots.append(0)
    dfs(info, shots, n, i + 1)
    shots.pop()


def solution(n, info):
    global answer

    dfs(info, [], n, 0)

    if not answer:
        return [-1]

    answer.sort(key=lambda x: x[::-1], reverse=True)

    return answer[0]