[PROMGRAMMERS] 2022 BLIND RECRUITMENT : 양궁대회 Python

이 문제는 문제에서 어피 치과 과녁을 쏜 이후에 라이언이 과녁을 쏘는데 문제에 규칙에 따라서 라이언이 최대 점수차로 이기게 과녁을 쏠려면 어떻게 점수를 얻어야 할지 구하는 문제이다.

출처 : 프로그래머스 (이미지가 너무귀엽다)

이 문제를 보면서 어떻게 구현할지 고민을 했는데 나에게 힌트가 됐던 점은 점수가 1에서 10까지 있다는 것과 오직 점수 얻는 방식이 상대편(어피치) 보다 많이 그 점수를 맞췄을 때 딱 그 점수만 얻는다는 점이다.

예를 들면 어피치가 10점 3발, 라이언이 10점 4발을 맞춘다면 점수는 라이언만 10점을 얻게된다는 점이다. 즉, 10개의 점수판 중에서 1점을 획득한다/ 못한다, 2점을 획득한다 / 못한다 이런 식으로 경우의 수가 2의 10 제곱으로 완전 탐색을 할 수 있다는 점이 나에게 힌트였다.

나는 위의 아이디어를 바탕으로 완전탐색으로 구현하였다. 추가로 더 고민했어야 했던 부분은 동점이면 어피치가 점수를 받는다는 점과 (이 부분은 비교 연산할 때 조금만 신경 쓰면 쉽게 구현할 수 있다.)  최대 점수차가 여러 개일 때,  낮은 점수의 과녁을 많이 맞힌 경우를 정답으로 인정하는 부분이었다.

나는 두 번째 부분을 완전 탐색 종료 조건에 for문으로 비교하며 결정하는 과정을 거쳐서 정답을 구했다. 이를 코드로 나타낸다면 아래와 같다.

def solution(n, info):

    def brut(n, lion, idx): # 남은 화살수, 과녁, 현재 idx
        nonlocal gap, answer

        if idx > 10: # 정지조건

            # 화살이 남은경우 마지막에 다쏜다고 가정
            if n > 0:
                lion[10] += n
            score_apeach = 0
            score_lion = 0
            # 점수 세기
            for idx in range(0,11):
                if lion[idx] > apeach[idx]:
                    score_lion += 10-idx
                elif apeach[idx]:
                    score_apeach += 10-idx

            if score_lion - score_apeach > gap:
                gap = score_lion - score_apeach
                answer = lion[:]

            # 낮은 점수를 많이 쏜 경우 정답 최신화
            elif score_lion - score_apeach == gap:
                for i in range(10,-1,-1):
                    if answer[i] < lion[i]:
                        answer = lion[:]
                        break
                    elif answer[i] > lion[i]:
                        break

            if n > 0:
                lion[10] -= n
            return

        # 이번 idx(점수) 어피치를 이기는 경우와 지는경우 모두 탐색
        ## 이기는 경우
        if apeach[idx] + 1 <= n:
            lion[idx] = apeach[idx] + 1
            brut(n-apeach[idx]-1, lion, idx+1)
            lion[idx] = 0
        ## 지는 경우
        brut(n, lion, idx+1)

    apeach = info
    lion = [0] * 11
    gap = 1
    answer = []
    brut(n, lion, 0)

    return answer if answer else [-1]

 

처음에 코드를 구현할 때 내방식으로 완전 탐색을 하면 화살을 다 쏘지않고 정답을 기록해버리는 경우가 있어서 오류가 났다. 다행히 테스트케이스로 확인이 됐기 때문에 고칠 수 있었지만 테스트케이스로 찾지 못했다면 또 한참 해맷을 것이다.

특히, 이런 완전탐색 문제나 구현 문제에서는 문제와 내 코드를 꼼꼼히 보면서 이렇게 짜면 어떤 엣지 케이스를 놓칠지 고민하면서 푸는 연습을 해야 할 것 같다.