[파이썬] 카카오코테 2022 양궁 대회

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

개인적으로 lv2보다는lv3 보이는 문제

from collections import defaultdict

def solution(n, info):
    global ryan, answer, mx
    ryan = [0]* len(info)
    answer = defaultdict(list)
    mx = 0
    
    def do_score(ryan, info):
        ryan_score = 0
        apeach_score = 0
        for i in range(11):
            if ryan[i] == 0 and info[i] == 0:
                continue
            elif ryan[i]>info[i]:
                ryan_score += 10-i
            else:
                apeach_score += 10-i
        if ryan_score > apeach_score:
            return ryan_score - apeach_score
        return 0
           
           
    def dfs(idx,n):
        global mx
        if n <= 0: # 가지치기
            ryan_result = do_score(ryan,info)
            if ryan_result:
                mx = max(mx, ryan_result)
                answer[ryan_result].append(ryan[:])
            return
        if idx == 10:
            if n > 0:
                ryan[idx] += n
            ryan_result = do_score(ryan,info)
            if ryan_result:
                mx = max(mx, ryan_result)
                answer[ryan_result].append(ryan[:])
            if n >0:
                ryan[idx] -= n
            return
        winning=min(info[idx]+1,n)
        ryan[idx] += winning
        dfs(idx+1, n-winning)
        ryan[idx] -= winning
        dfs(idx+1, n)
        
    dfs(0,n)
    par = answer[mx]
    
    return sorted(par, key = lambda x : x[::-1], reverse=True)[0] if par else [-1]

세 가지 중요한 포인트를 기록한다.

1. 먼저, do_score에 결함이 있었다. for r, i in zip(ryan, info) 로 잡은 뒤에 점차로 10에서부터 1까지 스코어를 줄여가면서 기록하는 것을 for 문에서 aim= 10 으로 시작한뒤 if문 가장 아래에서 aim-=1을 반복해주는 구조로 짰었는데, continue 조건을 만난 경우 aim -=1을 수행할 수 없었기 때문에 문제가 발생했다. (디버깅하는데 엄청 오래걸렸다. for문의 구조를 range로 짠 것이 아니라 zip으로 짠 것이 실수였다.)
2. 문제를 잘 못 읽었다. 단순히 ryan의 스코어가 최대일 때를 기준으로 동률을 따지는게 아니라, ryan - apeach의 차이가 최대일 때를 기준으로 동률을 따져야 하는 것이었다. (이 것은 테케 돌려보고 거의 바로 알았다)
3. 마지막에 sorting 에서 실패가 있었다. 이것은 아예 인지를 하지 못하고 있었다. 내일 비교 확인해보자. 나는 그냥 sort 하면될줄 알았는데 그렇게 해서는 안되고, sorted(par)[0] 으로 해서는 안되고 sorted(par, key = lambda x : x[::-1], reverse=True)[0] 이렇게 해야 한다는 것이었다. 8번 18번 테케에서 틀렸는데 반례를 찾아볼 수 있을 것 같다.
4. 마지막에 남아있는 n을 더해주는 부분을 원복 시키지 못해서 문제가 발생했다. solution 에서 처리된 것이 아니라 기저사례(base case)에서 처리해버리는 바람에 파악하지 못했다. (디버깅 오래걸림) 더 깔끔한 처리 방법 -> array 자체에 변경을 가하지 말고 답안에만 반영해 넣어두기!

무엇보다 가장 핵심이 되는 부분은 여기다.

 ryan[idx] += winning
 dfs(idx+1, n-winning)
 ryan[idx] -= winning
 dfs(idx+1, n)

참고

pythonic 한 답안 : 말도 안되게 편함.