2022 카카오 신입공채 코딩테스트(4)

이 문제부터 조금은 어려워진 것 같다.
문제 내용은 링크로 대체 (문제 링크)

문제

• 라이언이 어피치보다 더 많은 점수를 얻는 경우를 출력하시오.
• 해당 점수에 더 많은 화살을 맞춰야 점수 획득
• 라이언과 어피치가 같은 점수에 동일 갯수를 맞춘 경우 어피치가 점수 획득
• 점수 총합이 높으면 우승
• 라이언이 가장 큰 점수 차이로 우승하기 위한 경우 출력
• 같은 점수차가 있다면 낮은 점수에 더 많은 화살을 맞춘 경우 선택
• 라이언이 우승 불가하면 [-1] 출력

1. 중복 조합

첫 번째 풀이는 중복 조합을 통해 라이언이 과녁에 화살을 맞출 모든 경우의 수를 나열한 뒤 점수를 계산하는 것이다. 이 경우 ${}_nH_{11} = {}_{n+10}C_{10}$ 이므로 $n$의 최댓값 10에 따라 최악의 경우에는 184,756 가지의 경우의 수를 탐색해야 함.

from itertools import combinations_with_replacement

def solution(n, info):
    answer = [-1]
    gap = 0
    comb_cases = combinations_with_replacement([i for i in range(11)], n)
    
    for case in comb_cases:
        ryan_shot = [0] * 11
        for idx in case:
            ryan_shot[idx] += 1
        ryan_shot = ryan_shot[::-1]
            
        muzi_score, ryan_score= 0, 0
        for i, (muzi, ryan) in enumerate(zip(info, ryan_shot)):
            if ryan > muzi:
                ryan_score += (10 - i)
            elif ryan <= muzi and muzi != 0:
                    muzi_score += (10 - i)
            
        if ryan_score > muzi_score and gap < (ryan_score - muzi_score):
            answer = ryan_shot
            gap = ryan_score - muzi_score
    return answer

2. 비트연산 활용

비트 연산을 활용해 라이언이 어느 점수에서 이길 것인지 판단하도록 하는 풀이이다. 이 경우는 10점 까지의 점수이므로 $2^{10}$, 총 1024개의 경우의 수만 탐색하면 된다.

def solution(n, info):
    answer = [0] * 11
    ryan_shot = [0] * 11
    gap = 0

    for subset in range(1, 1 << 10):
        ryan = 0
        apeach = 0
        count = 0

        for i in range(10):
            if subset & (1 << i):
                ryan += 10 - i
                ryan_shot[i] = info[i] + 1
                count += ryan_shot[i]
            else:
                ryan_shot[i] = 0
                
                if info[i]:
                    apeach += 10 - i
        
        if count > n:
            continue

        ryan_shot[10] = n - count

        if ryan - apeach > gap:
            answer = ryan_shot[:]
            gap = ryan - apeach
        
        elif ryan - apeach == gap: # 점수차가 동일한 경우 낮은 점수를 더 많이 맞춘 경우 우승
            for idx in reversed(range(11)):
                if ryan_shot[idx] > answer[idx]:
                    answer = ryan_shot[:]
                    gap = ryan - apeach
                    break
                elif ryan_shot[idx] < answer[idx]:
                    break              
    
    if gap == 0:
        return [-1]
    return answer

---

비트연산 풀이의 경우 인터넷에서 해설을 보고 알게 된 풀이인데, 비트 연산을 알아두면 다른 문제 풀이에도 도움이 많이 될 것 같다.