[PS] 양궁대회

문제 링크

코드

def solution(n, info):
    answer = []
    max_diff = 0

    stack = [([], 0, n)]
    while stack:
        picked, idx, left = stack.pop()
        if idx == 10:
            picked.append(left)
            
            
            def calculate(): 
                ryan = 0
                apeach = 0
                for i, (a, r) in enumerate(zip(info, picked)):
                    point = 10 - i
                    if a == 0 and r == 0:
                        continue
                    if a < r:
                        ryan += point
                    else:
                        apeach += point
                return ryan - apeach
            
            
            diff = calculate()
            if diff > max_diff:
                max_diff = diff
                answer = picked
            elif diff == max_diff:
                
                
                def compare():
                    before = reversed(answer)
                    cur = reversed(picked)
                    
                    for b, c in zip(before, cur):
                        if b > c:
                            return False
                        elif c > b:
                            return True
                        
                        
                if compare():
                    max_diff = diff
>                     answer = picked
        else:
            stack.append((picked + [0], idx + 1, left))
            arrows_to_point = info[idx] + 1
            if left >= arrows_to_point:
                stack.append((picked + [arrows_to_point], idx + 1, left - arrows_to_point))

    if max_diff == 0:
        return [-1]
    return answer

리뷰

처음에는 DP문제라고 생각이 고정되어 완전탐색으로 푸는 방법에 대해 고려하지 못했다. 완전탐색으로 풀 수 있는 문제인지 먼저 확인해야겠다.
또 8번, 18번 테스트 케이스에서 계속 오류가 발생했는데 이는 더 낮은 숫자를 많이 맞춘 경우를 구하라는 조건 때문이었다. diff >= max_diff라고 했을 때 나중에 나오는게 더 낮은 숫자가 많을 것이라고 쉽게 생각했던게 문제였다.