[카카오 코테 2022 | python] 양궁대회

• 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/92342
• level2
• 2022 KAKAO BLIND RECRUITMENT

Q1) 어떤 문제인가요?
A1) 이 문제는 주어진 화살 수(n)만큼 라이언이 과녁에 화살을 쏠 때, 어피치와의 점수 차이를 가장 크게 만들어야 하는 문제입니다. 단순한 완전 탐색으로 모든 경우의 수를 계산하면서, 라이언이 얻을 수 있는 점수를 평가하고, 그 중 어피치를 이길 수 있는 조합 중
가장 점수 차가 큰 경우를 선택해야 합니다.

Q2) 어떻게 풀 계획이신가요?
A2-1)
- 먼저 0~10점까지 11개의 점수에 대해 라이언이 몇 발을 쏠지 경우의 수를 모두 탐색합니다.
- 각 경우에 대해 점수를 계산하며, 라이언이 이긴 경우에는 점수 차이를 기록해 최적 해를 찾습니다.
- 탐색 도중에는 남은 화살 수를 넘지 않도록 하고, 마지막에는 남은 화살을 0점에 몰아줍니다.
- 여러 경우가 동일한 점수 차이를 만들면, 낮은 점수부터 많이 맞힌 경우를 우선하는 사전순 비교로 결과를 선택합니다.
- 모든 경우에서 이길 수 없다면 [-1]을 반환합니다.

A2-2)
모든 점수판(0~10점)을 보면서, 이 점수에서 이기려고 화살을 쏠지, 아니면 이 점수는 포기할지 두 가지 선택을 계속하면서 화살 n발을 다 쏘는 방법을 "전부 시도"해보려고 합니다.

 

 

🌀 최적 코드

def solution(n, info):
    answer = []
    max_diff = 0  # 최대 점수차 저장

    def dfs(index, remain, ryan): # 지금 처리 중인 점수(0이면 10점, 10이면 0점), 남은 화살 수, 라이언이 쏜 화살을 저장하는 리스트
        nonlocal answer, max_diff # 전역 변수 사용

        if index == 11:  # 0점까지 다 처리했으면
            if remain > 0:
                ryan[10] += remain  # 남은 화살은 0점에 몰빵 → 0점을 맞춰도 아무도 점수를 얻지 못하므로 상관없음

            # 점수 계산
            apeach_score, ryan_score = 0, 0
            for i in range(11):
                if info[i] == 0 and ryan[i] == 0: # 어피치도, 라이언도 그 점수에 안 쐈으면 → 그냥 넘어감
                    continue
                if ryan[i] > info[i]: # 라이언이 더 많이 쐈을 경우
                    ryan_score += (10 - i)
                else:
                    apeach_score += (10 - i)

            diff = ryan_score - apeach_score

            if diff > 0: # 라이언이 이긴 경우에만 저장
                if diff > max_diff: # 점수차가 더 크면 바로 저장
                    max_diff = diff
                    answer = ryan[:]
                elif diff == max_diff:
                    # 제한사항: 라이언이 가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지 일 경우, 가장 낮은 점수를 더 많이 맞힌 경우를 return 해주세요.
                    # 동점일 때는 0점부터 비교해서 더 많이 쏜 경우 선택해요!
                    for i in range(10, -1, -1):
                        if ryan[i] > answer[i]:
                            answer = ryan[:]
                            break
                        elif ryan[i] < answer[i]:
                            break
            if remain > 0:
                ryan[10] -= remain  # ryan[10]에 몰빵했던 남은 화살을 다시 빼줍니다.
            return

        # 라이언이 이 점수 이기려면: 어피치보다 1발 더 쏘기
        if remain > info[index]:
            ryan[index] = info[index] + 1
            dfs(index + 1, remain - ryan[index], ryan)
            ryan[index] = 0  # 백트래킹, 없었던걸로 돌아가서 점수를 포기한 경우도 계산하자!

        # 이 점수 포기
        dfs(index + 1, remain, ryan)

    dfs(0, n, [0]*11)

    return answer if answer else [-1]