[Python | Level2] 양궁대회 / 2022 KAKAO BLIND RECRUITMENT

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

프로그래머스

---

문제 설명

카카오배 양궁대회가 열렸습니다.
라이언은 저번 카카오배 양궁대회 우승자이고 이번 대회에도 결승전까지 올라왔습니다. 결승전 상대는 어피치입니다.
카카오배 양궁대회 운영위원회는 한 선수의 연속 우승보다는 다양한 선수들이 양궁대회에서 우승하기를 원합니다. 따라서, 양궁대회 운영위원회는 결승전 규칙을 전 대회 우승자인 라이언에게 불리하게 다음과 같이 정했습니다.

1. 어피치가 화살 n발을 다 쏜 후에 라이언이 화살 n발을 쏩니다.
2. 점수를 계산합니다.
   1. 과녁판은 아래 사진처럼 생겼으며 가장 작은 원의 과녁 점수는 10점이고 가장 큰 원의 바깥쪽은 과녁 점수가 0점입니다.

      

   2. 만약, k(k는 1~10사이의 자연수)점을 어피치가 a발을 맞혔고 라이언이 b발을 맞혔을 경우 더 많은 화살을 k점에 맞힌 선수가 k 점을 가져갑니다. 단, a = b일 경우는 어피치가 k점을 가져갑니다. k점을 여러 발 맞혀도 k점 보다 많은 점수를 가져가는 게 아니고 k점만 가져가는 것을 유의하세요. 또한 a = b = 0 인 경우, 즉, 라이언과 어피치 모두 k점에 단 하나의 화살도 맞히지 못한 경우는 어느 누구도 k점을 가져가지 않습니다.
      • 예를 들어, 어피치가 10점을 2발 맞혔고 라이언도 10점을 2발 맞혔을 경우 어피치가 10점을 가져갑니다.
      • 다른 예로, 어피치가 10점을 0발 맞혔고 라이언이 10점을 2발 맞혔을 경우 라이언이 10점을 가져갑니다.
   3. 모든 과녁 점수에 대하여 각 선수의 최종 점수를 계산합니다.
3. 최종 점수가 더 높은 선수를 우승자로 결정합니다. 단, 최종 점수가 같을 경우 어피치를 우승자로 결정합니다.

 

현재 상황은 어피치가 화살 n발을 다 쏜 후이고 라이언이 화살을 쏠 차례입니다.
라이언은 어피치를 가장 큰 점수 차이로 이기기 위해서 n발의 화살을 어떤 과녁 점수에 맞혀야 하는지를 구하려고 합니다.

화살의 개수를 담은 자연수 n, 어피치가 맞힌 과녁 점수의 개수를 10점부터 0점까지 순서대로 담은 정수 배열 info가 매개변수로 주어집니다. 이때, 라이언이 가장 큰 점수 차이로 우승하기 위해 n발의 화살을 어떤 과녁 점수에 맞혀야 하는지를 10점부터 0점까지 순서대로 정수 배열에 담아 return 하도록 solution 함수를 완성해 주세요. 만약, 라이언이 우승할 수 없는 경우(무조건 지거나 비기는 경우)는 [-1]을 return 해주세요.

---

제한사항

• 1 ≤ n ≤ 10
• info의 길이 = 11
  • 0 ≤ info의 원소 ≤ n
  • info의 원소 총합 = n
  • info의 i번째 원소는 과녁의 10 - i 점을 맞힌 화살 개수입니다. ( i는 0~10 사이의 정수입니다.)
• 라이언이 우승할 방법이 있는 경우, return 할 정수 배열의 길이는 11입니다.
  • 0 ≤ return할 정수 배열의 원소 ≤ n
  • return할 정수 배열의 원소 총합 = n (꼭 n발을 다 쏴야 합니다.)
  • return할 정수 배열의 i번째 원소는 과녁의 10 - i 점을 맞힌 화살 개수입니다. ( i는 0~10 사이의 정수입니다.)
  • 라이언이 가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지 일 경우, 가장 낮은 점수를 더 많이 맞힌 경우를 return 해주세요.
    • 가장 낮은 점수를 맞힌 개수가 같을 경우 계속해서 그다음으로 낮은 점수를 더 많이 맞힌 경우를 return 해주세요.
    • 예를 들어, [2,3,1,0,0,0,0,1,3,0,0]과 [2,1,0,2,0,0,0,2,3,0,0]를 비교하면 [2,1,0,2,0,0,0,2,3,0,0]를 return 해야 합니다.
    • 다른 예로, [0,0,2,3,4,1,0,0,0,0,0]과 [9,0,0,0,0,0,0,0,1,0,0]를 비교하면[9,0,0,0,0,0,0,0,1,0,0]를 return 해야 합니다.
• 라이언이 우승할 방법이 없는 경우, return 할 정수 배열의 길이는 1입니다.
  • 라이언이 어떻게 화살을 쏘든 라이언의 점수가 어피치의 점수보다 낮거나 같으면 [-1]을 return 해야 합니다.

---

문제 풀이

이 문제를 처음 봤을 때 라이언이 이기기 위한 화살 배분 방법은 어떻게 정해질까? 라는 것을 생각했고 화살 수보다 점수가 더 높아지게끔 쏘면 되지 않을까 싶었지만 실제로는 화살 수 제약과 정렬 조건(점수 차, 낮은 점수 우선)까지 고려해야 하므로 단일 기준으로는 판단할 수 없었다.

우선 한 점수 구간에서 누가 점수를 가져가는지는 단순한 다수결이지만 그에 따른 전체 점수 차와 이길 수 있는지 여부, 그리고 이긴 경우들 중에서 어떤 분배가 '더 나은 결과'인지를 판단해야 한다. 즉, 단순히 어떤 구간에서 이길 수 있냐만 따지는 것이 아니라 전체 분배가 어떤 결과를 만들고 그 결과가 최선인지를 함께 봐야 한다.

여기서 떠오른 것은 2가지였는데

1. 화살을 각 점수에 어떻게 배분해야 하나?
   → 선택지는 점수 구간마다 "이길 것인지 말 것인지"를 판단하는 것. 모든 구간에서 이기려고 해봤자 화살이 부족하므로 결국 어떤 구간을 포기하고, 어떤 구간에 집중할지를 조합적으로 판단해야 함.
   → 특히 어피치보다 1발 이상을 더 쏴야 해당 점수를 가져갈 수 있으므로, 현재 남은 화살보다 더 많은 화살이 필요한 구간은 아예 건너뛰는 게 낫다. 이렇게 불필요한 경우를 사전에 차단하면 탐색 효율도 올라가고, 조건 위반도 막을 수 있다.
2. 가능한 모든 배분을 다 시도해봐야 하나?
   → 조건을 보면서 '화살을 최대한 효율적으로 써야 한다', '낮은 점수에 많이 쏘는 경우를 우선한다' 등의 규칙이 눈에 들어오는데, 이런 규칙들이 있더라도 결국 정답은 경우의 수 전체를 살펴본 뒤 조건에 맞는 최적의 분배를 찾는 것이라는 판단에 도달했음.
   → 문제 핵심은 결국 완전탐색 기반의 조합 최적화다. 규칙이 있어도 해답은 일일이 조합을 생성한 뒤 그중 최적인 걸 선별하는 구조다.

결론적으로 이 문제는 각 점수 구간에서 쏠지 말지 결정하는 2가지 선택을 11번 반복하는 문제이며, 화살 수를 초과하지 않는 선에서 DFS로 모든 가능한 분배를 탐색하고 그 중에서 조건에 맞는 최적의 분배를 찾는 구조가 적합하다.

---

구현

1. DFS로 가능한 모든 화살 분배 경우의 수를 탐색
   0점부터 10점까지 총 11개의 점수 구간에서 라이언이 쏠 수 있는 경우를 생각해본다. 각 점수 구간마다 “화살을 쏜다/안 쏜다”의 선택을 하며, 주어진 n발을 초과하지 않도록 한다.
   → 점수 구간마다 라이언이 쏠지 말지를 결정하고, 라이언이 점수를 얻으려면 어피치보다 정확히 1발 이상 더 쏴야 하므로 그 조건을 만족하지 못하는 경우는 건너뛴다. DFS에서 lion_info는 매 분기마다 복사해서 넘기도록 하고, 이전 상태에 영향이 가지 않도록 처리한다.
2. 점수 계산
   매 경우마다 어피치와 라이언의 점수를 계산하여 라이언이 이긴다면 점수 차이를 저장한다. 점수는 각 구간에서 화살 개수로 결정되며, 라이언이 더 많이 쐈을 때만 점수를 가져간다.
   → 점수를 계산할 때 어피치와 라이언이 모두 0발 쏜 경우는 무시해야 하고, 라이언이 어피치보다 화살을 많이 쏜 경우에만 점수를 얻는다. 점수는 10점부터 0점까지 계산하고, 어피치와 라이언 점수를 따로 누적한 뒤 비교한다.
3. 최적 해 조건 비교
   점수 차이가 현재 최대보다 크면 갱신하고, 같을 경우에는 낮은 점수에 더 많이 쏜 분배를 선택한다.
   → 낮은 점수에 더 많이 쏜 분배를 선택하려면 10점부터 0점까지 역순으로 비교해서 더 뒤에서 많이 쏜 분배를 선택하는 식으로 처리한다. 이게 tie-break 조건이다.
4. 남은 화살 처리
   DFS 종료 시점에 화살이 남아 있다면 가장 낮은 점수(0점)에 몰아서 사용한다. 이는 문제에서 요구하는 조건 중 “여러 답이 가능하면 낮은 점수에 더 많이 쏜 분배를 우선”하는 조건과 일치한다.
   → 점수 계산에는 영향 없지만, 결과 비교 시 낮은 점수 우선 조건을 만족하기 위해 반드시 필요하다.

이 문제에서는 dfs() 함수 내부에서 바깥 함수인 solution()의 지역 변수 max_diff와 answer를 수정해야 하므로 nonlocal 키워드를 사용했다. nonlocal은 중첩 함수에서 바로 바깥 함수의 지역 변수에 접근하고 수정할 때 사용된다.

def solution(n, info):
    from copy import deepcopy

    max_diff = 0
    answer = [-1]
    
    def dfs(idx, arrows_left, lion_info):
        nonlocal max_diff, answer

        if idx == 11:
            if arrows_left > 0:
                lion_info[10] += arrows_left  # 남은 화살은 0점에 다 쏨

            # 점수 계산
            apeach_score, lion_score = 0, 0
            for i in range(11):
                if info[i] == 0 and lion_info[i] == 0:
                    continue
                if info[i] >= lion_info[i]:
                    apeach_score += 10 - i
                else:
                    lion_score += 10 - i

            if lion_score > apeach_score:
                diff = lion_score - apeach_score
                if diff > max_diff:
                    max_diff = diff
                    answer = lion_info[:]
                elif diff == max_diff:
                    # 더 낮은 점수를 많이 맞힌 경우를 선택
                    for i in range(10, -1, -1):
                        if lion_info[i] > answer[i]:
                            answer = lion_info[:]
                            break
                        elif lion_info[i] < answer[i]:
                            break

            if arrows_left > 0:
                lion_info[10] -= arrows_left  # 복원

            return

        # 화살 안 쏘는 경우
        dfs(idx + 1, arrows_left, lion_info[:])

        # 화살 쏘는 경우 (이기려면 info[idx] + 1개 이상 필요)
        if arrows_left > info[idx]:
            lion_info[idx] = info[idx] + 1
            dfs(idx + 1, arrows_left - lion_info[idx], lion_info[:])
            lion_info[idx] = 0  # 복원

    dfs(0, n, [0] * 11)

    return answer