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

1) 문제 접근 방법

- 이 문제 같은 경우는 시간 초과를 나지 않도록 주의하는 것이 중요하다

  시간 초과가 나지 않으려면, 특정 케이스, 즉, 문제에서 요구하는 조건에 맞는 케이스만 탐색하도록 하면 된다

  어피치가 맞힌 점수의 개수는 info 배열에 담겨 있다

  그리고 라이언은 어피치가 맞힌 개수보다 하나까지만 초과하는 케이스만 탐색하면 된다.

  왜냐하면 두 개 이상 초과한다면, 어차피 하나까지만 초과하면 이기므로, 불필요하기 때문이다. 

  또한 n이 0미만일 때의 return을 해주는 것과, pos가 11일때 return을 해주는 것에 주의해야 한다

  즉, 시간 초과가 나지 않는 효율적인 코드를 작성하는 것이 제일 중요하다. 

  

2-1) 맞은 소스 코드

ans = [0]*20
maxGap = 0

def dfs(pos, n, info, ryan):
    
    if n < 0:
        return 
    
    global maxGap 
    
    if n == 0:
        
        apeachCnt = 0
        ryanCnt = 0 
        
        
        for i in range(0, 11):
            if info[i] == 0 and ryan[i] == 0:
                continue 
            
            if info[i] >= ryan[i]:
                apeachCnt += (10-i)
            else:
                ryanCnt += (10-i)
                
        
        if apeachCnt < ryanCnt: 
            gap = ryanCnt - apeachCnt 
            
            if maxGap < gap:
                maxGap = gap 
                
                ans.clear()
                for i in range(0, 11):
                    ans.append(ryan[i])
            elif maxGap == gap:
            
                change = False 
                
                for i in range(10, -1, -1):
                    if ans[i] > ryan[i]:
                        break
                    elif ans[i] < ryan[i]:
                        change = True 
                        break 
                
                if change == True:
                    ans.clear()
                    for i in range(0, 11):
                        ans.append(ryan[i])
                
        return 
    
    if pos == 11:
        return 
    
    
    
    ryan[pos] += (info[pos]+1)
    dfs(pos+1, n-ryan[pos], info, ryan)
    ryan[pos] -= (info[pos]+1)
    
    for i in range(info[pos], -1, -1):
        ryan[pos] += i
        dfs(pos+1, n-i, info, ryan)
        ryan[pos] -= i    
            
            


def solution(n, info):
    
    ryan = [0]*20
    
    dfs(0, n, info, ryan)
    
    if maxGap == 0:
        return [-1]
    else:
        return ans