프로그래머스 Level 2 | 2022 KAKAO BLIND RECRUITMENT | 양궁대회 | Python

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

문제 파악

양궁대회를 한다고 한다.
라이언이 전 챔피언
도전자가 어피치이다.

도전자인 어피치에게 어드밴티지를 준다고 한다.

• 어피치가 먼저 n발 쏘고, 라이언이 그다음에 n발 쏜다.

<과녁>

k점 구역에 더 많은 화살을 맞힌 선수가 k점을 가져간다.
단 둘이 동률일땐 도전자인 어피치가 가져간다. (어드밴티지)

현재 상황은 어피치가 먼저 쐈고,
우리는 라이언의 입장에서 문제를 풀어야 한다.
라이언의 입장에서 어떻게 과녁에 맞혀야 가장 큰 차이로 어피치를 이길 수 있을까? 를 구해야 한다.

---

<입출력 예>

n은 몇번 화살을 쏠 지
info의 인덱스는 각 [10,9,8,7,6,5,4,3,2,1,0] 점의 영역에 맞힌 화살 수를 의미한다.

즉 첫번째 입출력이 의미하는 바는
어피치가 5번의 화살을 쐈고, 10점 2개, 9점,8점,7점 영역에 각 한발씩 맞혔다는 의미이다.

이때 라이언의 입장에서 가장 큰 차이로 이기기 위해서는
이게 맞힌대로 점수를 주는 게 아니라 상대보다 더 많이 맞혀야 점수를 얻는 제도이기때문에
info의 인덱스가 작은 순서부터 하나씩 더 많이 맞혀야 한다.
즉 라이언의 info는 [3,2,0,0,0..] 가 된다.

n이 허락하는 선에서 상대의 info의 인덱스보다 1씩 더 키워야 하고, 만약 그게 안되는 인덱스가 있다면 그다음 info의 인덱스로 넘어가 1을 키우는 식으로 풀어야 할 것 같다.

근데 아니다.

라이언이 [0,2,2,0,1,0,0,0,0,0,0] 으로 쏘면 더 높은 점수 차이로 이길 수 있다.

그렇다면 완전 탐색일까?

---

<제한사항>

화살은 n발 꼭 다 쏴야 한다고 한다.
답이 여러개 나올 수 있는 경우, 가장 낮은 점수를 더 많이 맞힌 경우를 return 하라고 한다.
if len(ansnwer) >= 1:
real_answer.append(인덱스 비교해서 더 낮은애)
해야 할 것 같다.

마지막으로 라이언이 어떻게 쏘든 어피치를 이길 수 없다면 [-1]를 return 하라고 한다.
real_answer 를 [-1]로 초기화 하고 풀어보겠다.

---

해답 및 풀이

def solution(n, info):
    # 결과 전역 상태
    best_diff = -1
    best = [-1]  # 없음 표시

    # 동점일 때 타이브레이커: 낮은 점수(인덱스 10→0)부터 많이 쏜 쪽이 유리
    def better(a, b):
        # a가 더 좋으면 True
        for i in range(10, -1, -1):
            if a[i] != b[i]:
                return a[i] > b[i]
        return False  # 완전 동일

    # 현재까지의 점수차 계산을 incremental 하게 들고가도 되지만,
    # 구현 단순화를 위해 리프에서 한 번에 계산해도 n<=10이라 충분히 통과.
    def score_diff(ryan):
        a_score = 0
        r_score = 0
        for i in range(11):
            s = 10 - i
            if ryan[i] == 0 and info[i] == 0:
                continue
            if ryan[i] > info[i]:
                r_score += s
            else:
                a_score += s
        return r_score - a_score

    ryan = [0] * 11

    def dfs(i, remain):
        nonlocal best_diff, best

        # 마지막 칸(0점)까지 처리했거나 점수 10~0 다 결정했으면 평가
        if i == 11:
            # 남은 화살이 있다면 0점(인덱스 10)에 몰아넣는게 규칙이지만
            # 우리는 진행 중에만 호출되므로 여기선 remain==0이 정상
            diff = score_diff(ryan)
            if diff <= 0:
                return
            if diff > best_diff:
                best_diff = diff
                best = ryan[:]
            elif diff == best_diff and best != [-1] and better(ryan, best):
                best = ryan[:]
            return

        # 가지치기: 남은 칸(i..10)에 전부 몰아줘도 상태 공간 충분 (n<=10이라 과도한 pruning 불필요)
        # 1) 이 점수를 '이겨서' 가져간다: 어피치보다 1발 더
        need = info[i] + 1
        if need <= remain:
            ryan[i] = need
            dfs(i + 1, remain - need)
            ryan[i] = 0

        # 2) 포기한다: 0발
        # 단, 마지막 칸(0점: i=10)에서는 남은 화살 전부 몰아넣어야 유효한 배치
        if i == 10:
            ryan[i] = remain
            dfs(i + 1, 0)
            ryan[i] = 0
        else:
            dfs(i + 1, remain)

    dfs(0, n)
    return best