[프로그래머스][Level2] 양궁대회 (파이썬)

---

문제 출처

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

프로그래머스

---

문제를 스스로 해결하였는가?  ->  X

 한 달전, 처음 알고리즘 공부를 시작했을 때 DFS와 백트래킹에 대한 배경이 전혀 없는 상태에서 접했던 문제다. 프로그래머스에서 다른 사람의 풀이를 통해 솔루션을 참고했지만, 처음엔 솔루션을 보고 이해하는 것조차 힘들었다. 백준의 단계별 문제풀이에서 비슷한 알고리즘의 문제를 공부하고 다시 이 문제를 풀어보니 생각보다 잘 풀렸다. 아마 오랫동안 고민해서 소스코드 전체가 외워져서 그런 것 같다.   

---

필요한 배경 지식

• 백트래킹
• DFS

---

주의할 점

1. 라이언은 반드시 해당 과녁에 어피치보다 많은 개수를 맞춰야 점수를 가져갈 수 있다.
2. 해당 과녁에 라이언, 어피치 모두 화살을 맞추지 못했다면 아무도 점수를 가져가지 못한다.
3. 라이언이 가장 큰 점수 차로 이길 수 있는 방법이 여러 가지 일 경우 가장 낮은 점수를 더 많이 맞힌 경우를 return 해야한다.

---

풀이 과정

가장 먼저 라이언의 점수와 어피치의 점수가 주어졌을 때, 라이언의 점수를 계산하는 함수를 작성한다.

def score(ryan):
    s = 0
    for i in range(10):
        if apeach[i] == ryan[i] == 0: continue
        if apeach[i] < ryan[i]:
            s += 10-i
        else:
            s -= 10-i
    return s

다음으로 라이언의 점수를 ryan=[0,...,n] 부터 시작해 배열의 왼쪽으로 값을 하나씩 옮겨가며 점수를 계산하는 dfs 함수를 작성한다. 주의할 점 3에 의해 반드시 ryan=[0,...,n]에서 시작해야한다.

def dfs(idx, left):
    nonlocal maxi, answer
    if left == 0:
        s = score(ryan)
        if s > maxi:
            maxi = s
            answer = ryan[:]
        return
    # 11개 점수판을 모두 탐색했음에도 분배되지 않은 화살이 있다면 종료
    if left != 0 and idx==-1:
        return
    # 남아있는 과녁을 1개씩 줄여가며 dfs 수행
    for i in range(left, -1, -1):
        ryan[idx] = i
        dfs(idx-1, left-i)

---

전체 코드

def solution(n, apeach):
    ryan = [0] * 11
    answer = [0] * 11
    
    def score(ryan):
        s = 0
        for i in range(10):
            if apeach[i] == ryan[i] == 0: continue
            if apeach[i] < ryan[i]:
                s += 10-i
            else:
                s -= 10-i
        return s

    def dfs(idx, left):
        nonlocal maxi, answer
        if left == 0:
            s = score(ryan)
            if s > maxi:
                maxi = s
                answer = ryan[:]
            return
        if left != 0 and idx==-1:
            return
        for i in range(left, -1, -1):
            ryan[idx] = i
            dfs(idx-1, left-i)
            
    maxi = 0
    dfs(10, n)
    return answer if maxi != 0 else [-1]

---