[Programmers] 외벽 점검 - 백트래킹

문제 url: https://school.programmers.co.kr/learn/courses/30/lessons/92342?language=python3

프로그래머스

 

난이도: Lv.2

정답률: 37%

문제 설명

카카오배 양궁대회가 열렸습니다.

라이언은 저번 카카오배 양궁대회 우승자이고 이번 대회에도 결승전까지 올라왔습니다. 결승전 상대는 어피치입니다.

카카오배 양궁대회 운영위원회는 한 선수의 연속 우승보다는 다양한 선수들이 양궁대회에서 우승하기를 원합니다. 따라서, 양궁대회 운영위원회는 결승전 규칙을 전 대회 우승자인 라이언에게 불리하게 다음과 같이 정했습니다.

1. 어피치가 화살 n발을 다 쏜 후에 라이언이 화살 n발을 쏩니다.
2. 점수를 계산합니다.
3. 과녁판은 아래 사진처럼 생겼으며 가장 작은 원의 과녁 점수는 10점이고 가장 큰 원의 바깥쪽은 과녁 점수가 0점입니다.
4. 만약, k(k는 1~10사이의 자연수)점을 어피치가 a발을 맞혔고 라이언이 b발을 맞혔을 경우 더 많은 화살을 k점에 맞힌 선수가 k 점을 가져갑니다. 단, a = b일 경우는 어피치가 k점을 가져갑니다.
5. 모든 과녁 점수에 대하여 각 선수의 최종 점수를 계산합니다.
6. 최종 점수가 더 높은 선수를 우승자로 결정합니다. 단, 최종 점수가 같을 경우 어피치를 우승자로 결정합니다.
7. 현재 상황은 어피치가 화살 n발을 다 쏜 후이고 라이언이 화살을 쏠 차례입니다.
8. 라이언은 어피치를 가장 큰 점수 차이로 이기기 위해서 n발의 화살을 어떤 과녁 점수에 맞혀야 하는지를 구하려고 합니다.

입력

• 화살의 개수를 담은 자연수 n
• 어피치가 맞힌 과녁 점수의 개수를 10점부터 0점까지 순서대로 담은 정수 배열 info

출력

• 라이언이 가장 큰 점수 차이로 우승하기 위해 n발의 화살을 어떤 과녁 점수에 맞혀야 하는지를 10점부터 0점까지 순서대로 정수 배열에 담아 반환합니다.
• 라이언이 우승할 수 없는 경우(무조건 지거나 비기는 경우)는 [-1]을 반환합니다.

제한사항

• 1 ≤ n ≤ 10
• info의 길이 = 11
• 0 ≤ info[i] ≤ n
• info의 원소 총합 = n
• return할 정수 배열의 길이는 11
• 0 ≤ return[i] ≤ n
• return할 정수 배열의 원소 총합 = n
• 라이언이 가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지일 경우, 가장 낮은 점수를 더 많이 맞힌 경우를 반환합니다.
• 가장 낮은 점수를 맞힌 개수가 같을 경우 계속해서 그다음으로 낮은 점수를 더 많이 맞힌 경우를 반환합니다.
• 라이언이 우승할 방법이 없는 경우, 반환할 정수 배열의 길이는 1입니다.

입출력 예

n	info	result
5	[2,1,1,1,0,0,0,0,0,0,0]	[0,2,2,0,1,0,0,0,0,0,0]
1	[1,0,0,0,0,0,0,0,0,0,0]	[-1]
9	[0,0,1,2,0,1,1,1,1,1,1]	[1,1,2,0,1,2,2,0,0,0,0]
10	[0,0,0,0,0,0,0,0,3,4,3]	[1,1,1,1,1,1,1,1,0,0,2]

입출력 예 설명

예제 1

라이언이 어피치를 가장 큰 점수 차이로 이기기 위해 화살을 다음과 같이 쏠 경우 최적의 점수 차이를 얻을 수 있습니다.

과녁 점수	어피치가 맞힌 화살 개수	라이언이 맞힌 화살 개수	결과
10	2	0	어피치가 10점 획득
9	1	2	라이언이 9점 획득
8	1	2	라이언이 8점 획득
7	1	0	어피치가 7점 획득
6	0	1	라이언이 6점 획득
...

최종적으로 라이언이 6점 차이로 우승할 수 있습니다.

---

내 풀이

from itertools import combinations_with_replacement

def solution(n, info):
    answer = [-1]
    max_gap = -1

    # 화살 분배 경우의 수 탐색
    for combi in combinations_with_replacement(range(11), n):
        ryaninfo = [0] * 11  # 라이언의 점수 분배

        for i in combi:
            ryaninfo[10 - i] += 1  # 해당 점수에 화살 배치

        apeach, ryan = 0, 0
        for idx in range(11):
            if info[idx] == ryaninfo[idx] == 0:
                continue  # 둘 다 해당 점수를 얻지 않은 경우
            elif info[idx] >= ryaninfo[idx]:
                apeach += 10 - idx  # 어피치가 점수 가져감
            else:
                ryan += 10 - idx  # 라이언이 점수 가져감

        # 점수 차 계산 및 갱신
        if ryan > apeach:
            gap = ryan - apeach
            if gap > max_gap:  # 최대 점수 차 갱신
                max_gap = gap
                answer = ryaninfo

    return answer

---