[2022 Kakao Blind Recruitment] 양궁대회

어피치가 맞힌 과녁 점수가 들어간 배열 info 만이 주어진다. 이 배열 정보를 가지고 라이언이 가장 큰 점수 차이로 우승하기 위한 방법인 answer배열을 리턴해야 한다.

info배열의 첫번째 칸은 과녁 10점에 맞춘 개수를 나타내고 그 다음 칸은 10-i의 점을 나타낸다.

제한사항

• k점의 과녁을 더 많이 맞춘 사람이 k점을 가져간다.
• 0발을 맞히면 누구도 점수를 받지 못한다.
• 최종 점수가 같다면 어피치가 우승한다.
• 라이언이 가장 큰 점수차로 우승할 수 있는 방법이 여러 가지인 경우, 가장 낮은 점수를 더 많이 맞힌 경우를 리턴한다.
• 라이언이 우승할 방법이 없는 경우 '[-1]'을 리턴한다.

풀이

가장 먼저, 주어지는 화살 개수는 n개이다.
info의 길이 11만큼, 어피치의 점수를 계산한 다음 그것보다 더 높은 점수를 가질 수 있는 라이언의 양궁 점수 조합을 계산해보자.
0번째 인덱스에서 가장 마지막 점수가 위치하는 구간까지 탐색해야하니까 완전 탐색에다가 가장 많은 점수차이인 경우를 리턴해야하므로 백트래킹을 써야하지 않을까?
-> DFS?
-> combination?

• 가장 큰 점수 차일때, 가장 낮은 점수를 많이 맞추는 조건을 만족해야한다. 그렇다면 가장 큰 점수차가 난 시점에서 가장 낮은 점수에 화살을 다 소비하면된다.

주어진 예제 읽기

1트 코드

from itertools import combinations_with_replacement as cmb

def solution(n, info): 
    max_num = -1   # 라이언이 이길때 가장큰 점수 차이
    ans = []
    if n == 1:
        return [-1]
    
    # 라이언이 이기는 경우의 수
    for c in cmb(range(11), n):
        ryon = [0] * 11
        score = 0
        for i in c:
            ryon[i] += 1
        for j in range(11):
            if ryon[j] > info[j]:
                score += (10 - j)
            elif info[j] != 0:
                score -= (10 - j)
        if score <= 0: continue
        if score > max_num:
            score = max_num
            ans = ryon[1:-1]
    
    # 마지막에 점수 계산
    return ans