카카오 2022 블라인드, 양궁대회

풀이

# 문제요약
## 전우승자 라이언
## 중심부터 10점으로 시작
## 같은 지점에 더 많은 화살을 맞춘 자가 점수 한번만 가져간다.
## 화살의 갯수가 같으면 어피지가 가져간다.
## 화살을 둘다 한개도 못맞쳣으면 점수가 없다.
## 최종점수가 높은사람이 우승자, 최종점수가 같으면 어피치를 우승자로 결정
## i번째원소는 10-i 점을 맞힌 화살 갯수입니다.
## 라이언이 최대점수차이로 이기는 경우의 수를 구하라
## 경우의수가 여러가지라면 가장 낮은점수를 많이 맞힌 경우를 반환

# 풀이전략
## 가능한 조건을 모두 고려해 테스트해보면 답을 구할수 있다.
## 화살이 최대 10개라면, 10~0번까지 10번 중복해서 뽑을수 있다.

# combinations_with_replacement 함수로 중복조합을 뽑아서
# 적절한 시간복잡도로 문제를 해결할수 있다.
# 11 H 10 = 20 C 10 = 184756
from itertools import combinations_with_replacement

def solution(n, apeach_result):
    # 최고 점수는 10점이 이기 때문에
    # range함수에서 활용하기 위해 +1한다.
    MAX_SCORE = 11
    answer, difference = [-1], 0
    
    # combinations_with_replacement는 주어진 배열에서 첫번째 뽑아본다.
    # 여기서는 가장 작은 점수를 가진 숫자부터 뽑는다
    apeach_result = apeach_result[::-1]
    
    # 모든 case들에 대해 검사해본다.
    for case in combinations_with_replacement(range(MAX_SCORE), n):
        lion_result = [0]*MAX_SCORE
        lionScore, apeachScore = 0, 0
        
        # 뽑힌 결과로 라이언의 양궁 결과를 만든다.
        for score in case:
            lion_result[score] += 1
        
        for score in range(MAX_SCORE):
            # 둘다 0점이면 둘다 점수를 못엇는다.
            if lion_result[score]==0 and apeach_result[score]==0:
                continue
            # 어피치의 점수가 크거나 같으면 어피치의 점수가 된다.
            if lion_result[score] <= apeach_result[score]:
                apeachScore += score
            else:
                lionScore += score    
        
        # 라이언이 이기고, 차이가 크면 그냥 갱신해주면 된다.
        # 왜냐하면 작은 점수부터 뽑아 나가기 때문에
        # 가장 차이가 크면서, 가장 작은 점수를 많이 뽑은 결과가 된다.
        if lionScore-apeachScore > difference:
            difference = lionScore-apeachScore
            answer = lion_result

    # 다시 10점에서 0점의 순서로 맞춰서 반환해준다.
    # 만약 라이언이 이길수 없다면 갱신이 일어나지 않아 [-1]을 반환한다.
    return answer[::-1]