[프로그래머스] 양궁대회 - Python

🤔 문제

---

https://programmers.co.kr/learn/courses/30/lessons/92342

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

😀 풀이

---

해당 문제는 N의 크기가 10으로 작기 때문에 DFS로 완전 탐색을 하여도 문제가 없습니다. 

 

따라서 라이언이 과녁을 맞춰서 어피치의 점수를 뺏을지의 여부를 체크해가며 DFS 함수를 진행해 나아갔습니다.

 

10점부터 0점까지 전부 진행하면 라이언의 화살들이 어떻게 꽂혔는지, 즉 화살을 쏜 결과가 완성이 되는데 이를 바탕으로 어피치와 점수를 비교하여 점수 차를 확인했습니다. ( 풀이 코드에 calcScoreDiff 함수 ) 

 

점수 차를 확인한 후 이전의 결과들로 만들어진 최대 점수차보다 큰 경우 최대 점수차를 갱신하고 정답의 후보가 될 수 있는 라이언의 화살 결과를 answers 배열에 담습니다. 이때 최대 점수차가 새로 갱신되었으므로 이전에 만들고 있던 answers 배열은 전부 비우고 난 뒤 추가합니다.  ( answers 배열은 현재 구한 최대 점수차를 낼 수 있는 화살 결과 경우의 수를 담고 있습니다. )

 

또한 이전 결과들로 만들어진 최대 점수차와 같은 점수차가 나는 라이언의 화살 결과가 나오면 answers 배열에 단순 추가해줍니다.

 

DFS 과정을 마치고 나면 answers에는 정답 후보들이 있을 텐데 문제 조건 중 

 

라이언이 가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지 일 경우,

가장 낮은 점수를 더 많이 맞힌 경우를 return 해주세요.

 

위와 같은 조건이 있으므로 answers 배열을 적당한 방식( 풀이 코드 51 Line의 sort 함수 속 lambda 함수 )으로 정렬해준 뒤 답을 찾아내면 됩니다. 

 

💻 풀이 코드는 아래와 같습니다.

import copy

MAX_SCORE_DIFF = 0
answers = []

# 라이언과 어피치의 점수 차이를 계산하는 함수
def calcScoreDiff(info, myshots):
    enemyScore, myScore = 0, 0
    for i in range(11):
        if (info[i], myshots[i]) == (0, 0):
            continue
        if info[i] >= myshots[i]:
            enemyScore += (10 - i)
        else:
            myScore += (10 - i)
    return myScore - enemyScore

def dfs(info, myshots, n, i):
    global MAX_SCORE_DIFF, answers
    if i == 11:
        if n != 0:
            myshots[10] = n
        scoreDiff = calcScoreDiff(info, myshots)
        if scoreDiff <= 0:
            return
        result = copy.deepcopy(myshots)
        if scoreDiff > MAX_SCORE_DIFF:
            MAX_SCORE_DIFF = scoreDiff
            answers = [result]
            return
        if scoreDiff == MAX_SCORE_DIFF:
            answers.append(result)
        return

    # 점수 먹는 경우
    if info[i] < n:
        myshots.append(info[i] + 1)
        dfs(info, myshots, n - info[i] - 1, i + 1)
        myshots.pop()

    # 점수 안먹는 경우
    myshots.append(0)
    dfs(info, myshots, n, i + 1)
    myshots.pop()

def solution(n, info):
    global MAX_SCORE_DIFF, answers
    dfs(info, [], n, 0)
    if answers == []:
        return [-1]
    answers.sort(key = lambda x : x[::-1], reverse=True)
    return answers[0]