[프로그래머스][DFS] 양궁대회

양궁대회

프로그래머스

 

• 내 풀이
  • dfs로 점수 하나마다 cnt만큼 경우의 수 돌기
    • 화살 다 쓰면 어피치,라이언 점수 비교
    • if a==0 and b==0: continue
      • 비교하는 과정에서 이거 안넣어서 시간 엄청 뺏김…..조건을 잘 보자ㅠㅠ
  • 여러개일 때, 제일 낮은 점수를 가장 많이 쏜 경우를 출력
  • ⇒ reversed된 값을 오름차순 정렬해서 다시 reversed 함

from collections import defaultdict
def solution(n, info):
    answer =defaultdict(list)
    
    def dfs(cnt,tmp,idx):
        if cnt<=0:
            apeach=0
            lion=0
            for i,ab in enumerate(zip(info,tmp)):
                a,b=ab
                if a==0 and b==0:
                    continue
                if a>=b:
                    apeach+=(10-i)
                else:
                    lion+=(10-i)
                    
            if apeach>=lion:
                return
            else:
                answer[lion-apeach].append(list(reversed(tmp)))
                return
        
        if idx>10:
            return
        
        for k in range(cnt+1):
            tmp[idx]+=k
            dfs(cnt-k,tmp[:],idx+1)
            tmp[idx]-=k

        
    dfs(n,[0 for _ in range(11)],0)      
    
    if answer:
        maxKey=sorted(answer,reverse=True)[0]
        return list(reversed(sorted(answer[maxKey],reverse=True)[0]))
    else:
        return [-1]