[프로그래머스] 양궁대회 (파이썬 풀이)

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

프로그래머스

 

* 풀이 못 함

from itertools import combinations_with_replacement as cr

def solution(n, info):
    # 중복조합으로 모든 경우 탐색하면서 정답 갱신
    # 최대로 점수 차이가 클 때의 점수 분포 + 그 때의 점수 차이 값(max[-1])
    max = [-1] * 12
    for comb in cr(range(11), n):
        cur = [0] * 12
        # 점수별 화살 개수
        for c in comb:
            cur[10 - c] += 1
        
        # 점수 차이 계산
        for i in range(11):
            # 라이언 점수 획득
            if cur[i] > info[i]:
                cur[-1] += 10 - i
            # 어피치 점수 획득
            elif info[i] != 0:
                cur[-1] -= 10 - i
        
        # 라이언이 우승하지 못하는 경우
        if cur[-1] <= 0:
            continue
            
        # 기존의 점수 차이 최댓값을 갱신하는 경우
        if cur[::-1] > max[::-1]:
            max = cur

    return [-1] if max[-1] <= 0 else max[:-1]

• 아이디어: 0 ~ 10의 점수를 n번 중복 허용하여 뽑기 -> 11Hn(중복조합), 각 경우마다 어피치와 비교하여 최대 점수차이에 해당하는 경우 갱신
• 리스트끼리 비교 연산자(>, <)를 사용하면 앞에서부터 확인하면서 같으면 넘기고 최초로 다른 그 지점에서 부등호 방향이 맞으면 바로 True 반환하고 종료 (그 뒤는 고려하지 않음)

def solution(n, info):
    max = [-1] * 12
    for win in range(1 << 10):
        # 10 ~ 1의 점수별 화살 갯수, 0점 개수, 점수 차이
        cur = [0] * 10 + [n, 0]
        for i in range(10):
        	# 라이언 점수 획득
            if win & (1 << i):
                cur[-1] += 10 - i
                cur[-2] -= info[i] + 1
                cur[i] = info[i] + 1
            # 어피치 점수 획득
            elif info[i] != 0:
                cur[-1] -= 10 - i
                
        # 라이언이 지거나 화살을 n발 초과로 쏜 경우
        if cur[-1] <= 0 or cur[-2] < 0:
            continue
            
        # cur가 기존에 저장된 max보다 좋을 경우
        if cur[::-1] > max[::-1]:
        	max = cur

    return [-1] if max[-1] <= 0 else max[:-1]

• 아이디어: 1~10점 중에 라이언이 획득한다고 가정하는 점수들에 대해 필요한 화살이 n개를 넘지 않고, 가장 큰 점수 차이로 이기면서 가장 낮은 점수를 더 많이 맞힌 경우 반환
• 비트 연산을 이용해 점수를 획득하는 모든 경우에 대해 각 상황에서 어피치와 점수차이 계산
• 획득하는 점수에 대해서는 어피치보다 1개 더 맞히고, 그렇지 않은 점수는 0개를 맞히며, 나머지 화살은 가장 낮은 점수를 더 많이 맞히는 것이 좋으므로 모두 0점을 맞힌다고 가정
• 중복조합보다 고려할 경우가 훨씬 적으므로 시간 효율이 훨씬 좋음 (11Hn = 20C10 >> 2 ** 10 = 1024)