프로그래머스_양궁대회/Using Python 파이썬

Problem

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

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

About Problem

1. 과녁은 0 ~ 10점까지 총 11개의 종류로 구분된다

2. k(k는 1~10사이의 자연수)점을 어피치가 a발을 맞혔고 라이언이 b발을 맞혔을 경우 더 많은 화살을 k점에 맞힌 선수가 k 점을 가져갑니다.

3. a = b = 0 인 경우, 즉, 라이언과 어피치 모두 k점에 단 하나의 화살도 맞히지 못한 경우는 어느 누구도 k점을 가져가지 않습니다.

4. 최종 점수가 더 높은 선수를 우승자로 결정합니다. 단, 최종 점수가 같을 경우 어피치를 우승자로 결정합니다.

5. 라이언이 가장 큰 점수 차이로 우승하기 위해 n발의 화살을 어떤 과녁 점수에 맞혀야 하는지를 10점부터 0점까지 순서대로 정수 배열에 담아 return

6. 라이언이 우승할 수 없는 경우(무조건 지거나 비기는 경우)는 [-1]을 return 

7. 라이언이 가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지 일 경우, 가장 낮은 점수를 더 많이 맞힌 경우를 return 

 

이렇게 7가지 규칙을 생각해서 code를 구성하면 된다.

 

입출력 예)

 

Code

입출력 범위가 10 이하이므로 이건 거의 완탐이라고 생각하면 된다.

코드는 아래와 같고 설명은 코드에 적었다.

# 완탐(10개만 돌면 되기 때문에)
def solution(n, info):
    # 정답
    answer = []
    # 기본 차이를 1로 만들어야 이길 경우
    score_gap = 1

    # dfs
    def dfs(idx, last_num, now_info): # index, 남은 횟수, 현재정보
        # score_gap과 answer은 바꿔야 하므로 nonlocal로 사용해서 함수 안에서도 변경 할 수 있도록한다.
        nonlocal score_gap, answer
        # 맞출 과녁이 0밖에 안남았을 때
        if idx == 10:
            # 0에 몰빵해주기
            now_info[10] += last_num
            # 어피치와 라이언 스코어 비교
            lion_num = 0
            peach_num = 0
            for j in range(len(now_info) - 1):
                if now_info[j] > info[j]:
                    lion_num += 10 - j
                elif info[j]:
                    peach_num += 10 - j

            # 이번 갭차이가 더 클때
            if lion_num - peach_num > score_gap:
                score_gap = lion_num - peach_num
                answer = now_info[:]

            # 같은 갭일 떄에는 젤 작은 수가 어떤쪽이 많은지 생각 해야한다.
            elif lion_num - peach_num == score_gap:
                for j in range(len(now_info)-1, -1, -1):
                    if now_info[j] > answer[j]:
                        answer = now_info[:]
                        break
                    elif now_info[j] < answer[j]:
                        break
            now_info[10] -= last_num

        else:
            # 완탐 이번idx에 수를 넣을 경우와 안 넣을 경우
            if last_num >= info[idx] + 1:
                lst[idx] = info[idx] + 1
                dfs(idx + 1, last_num - 1 - info[idx], now_info)
                lst[idx] = 0
            dfs(idx + 1, last_num, now_info)


    # dfs
    lst = [0] * 11
    dfs(0, n, lst)
    if not answer:
        answer = [-1]

    return answer