import math

def solution(n, info):
    global answer, max_score_diff
    answer = [-1]
    max_score_diff = -math.inf # 가장 큰 점수차를 구하기 위한 변수

	# 라이언과 어피치의 점수차를 구하는 함수
    def get_score_diff(lion,apeech):
        lion_sum,apeech_sum=0,0
        for i in range(11):
            if lion[i] == 0 and apeech[i] == 0:
                continue
            if apeech[i] >= lion[i]:
                apeech_sum += 10-i
            else:
                lion_sum += 10-i
        return lion_sum - apeech_sum


    def dfs(idx,apeech,lion,cnt):
        global answer, max_score_diff
        
        
        if cnt < 0 :
            return
        if idx == 11:
        	# 화살이 남은 경우, 모두 0점 처리 한다
            lion[-1] += cnt
          
            score = get_score_diff(lion,apeech)
			# 라이언점수-어피치 점수차가 0보다 작으면 어피치가 이긴다
            if score <= 0:
                return 
                
            # 가장 큰 점수차이를 갱신한 경우
            if max_score_diff < score :
                max_score_diff = score
                answer=lion
                
            # 중요) 같은 점수차이인 경우, 즉 라이언이 가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지 일 경우,  !! 
            elif max_score_diff == score :
            
            	# 가장 낮은 점수를 더 많이 맞힌 경우를 찾는다
                min_score_idx = 0 
                for i in range(10,-1,-1):
                    if answer[i] !=0 or lion[i] !=0:
                        min_score_idx = i
                        break
                if answer[min_score_idx] < lion[min_score_idx]:
                    answer = lion[:]
            return

        new_lion1 = lion[:]
        new_lion1[idx] = apeech[idx]+1
        dfs(idx+1 , apeech , new_lion1,cnt - (apeech[idx]+1))

        new_lion2 = lion[:]
        new_lion2[idx] = 0
        dfs(idx+1,apeech,new_lion2,cnt)

    dfs(0,info,[0 for _ in range(11)],n)
    return answer

복기

테스트 케이스 8번과 18번에서 계~~속 실패가 났다. 몇 시간 붙잡고 생각을 해보니 로직이 잘못 되었다는 것을 알게되었다.

문제의 조건에서 "라이언이 가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지 일 경우, 가장 낮은 점수를 더 많이 맞힌 경우를 return 해주세요."라고 되있고 예시까지 들어줬는데, 대충 지나가고 말았다....

풀이

풀이는 생각보다 간단하다. 경우의 수를 줄이는 것이 핵심이다.

1. 라이언이 화살을 쏴 얻을 수 있는 경우의 수를 생각해보자

• 점수는 0점~10점까지 11개 경우
• 화살은 n개

라이언의 경우의 수를 10점부터 0점까지를 0발~n발로 증가시켜 구하게 되면 너~무 많은 경우의 수가 생긴다. (경우의 수를 구해봤는데 맞는지 모르겠다... n! x (n-1)! x (n-2)! ... x 11))

[n,0,0,0,0,0,0,0,0,0,0]
[n-1,1,0,0,0,0,0,0,0,0,0]
[n-1,0,1,0,0,0,0,0,0,0,0]
[n-1,0,0,1,0,0,0,0,0,0,0]
[n-1,0,0,0,1,0,0,0,0,0,0]
[n-2,2,0,0,0,0,0,0,0,0,0]
[n-2,1,1,0,0,0,0,0,0,0,0]
.....

2. 아무튼 경우의 수를 다음처럼 줄이는 것이 핵심이다.

라이언은 각 점수마다 어피치보다 +1번 더 맞추거나 0번 맞춘다

화살의 갯수를 신경쓰지 않고 구한 라이언의 전체 경우의 수는
2의 11제곱인 2048번이된다 (각 점수마다 +1번 맞춘 경우, 0번 맞춘 경우)

dfs 함수를 다음처럼 호출할 수 있다

new_lion1 = lion[:]
new_lion1[idx] = apeech[idx]+1
dfs(idx+1 , apeech , new_lion1,cnt - (apeech[idx]+1))

new_lion2 = lion[:]
new_lion2[idx] = 0
dfs(idx+1,apeech,new_lion2,cnt)

3. 최대 점수 차이를 갱신해준다.

• 여기서 중요한 점이 문제에서 라이언이 가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지 일 경우, 가장 낮은 점수를 더 많이 맞힌 경우를 return 해주세요.라고 했기 때문에 조건을 잘 지켜주어야한다.
• 아니면 8번 , 18번 케이스에서 걸리게 된다
• 다음 코드처럼 후보군이 여러개 인경우 가장 낮은 점수를 많이 맞힌 경우를 찾는다.

			# 가장 큰 점수차이를 갱신한 경우
            if max_score_diff < score :
                max_score_diff = score
                answer=lion
                
            # 중요) 같은 점수차이인 경우, 즉 라이언이 가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지 일 경우,  !! 
            elif max_score_diff == score :
            
            	# 가장 낮은 점수를 더 많이 맞힌 경우를 찾는다
                min_score_idx = 0 
                for i in range(10,-1,-1):
                    if answer[i] !=0 or lion[i] !=0:
                        min_score_idx = i
                        break
                if answer[min_score_idx] < lion[min_score_idx]:
                    answer = lion[:]
            return