프로그래머스 양궁 대회 파이썬

해답 코드

LIMIT=11   
max_scores_list=[]
max_score=0

# 어피치 점수와 재귀로 얻어낸 라이언 점수 현황을 비교하여 차이를 구한다.
def calculate_difference(ryan_scores:list,apeach_scores:list)->int:
    global LIMIT
    
    champion_score=0 # 라이언이 챔피언
    challenger_score=0 # 어피치가 도전자
    
    for i in range(LIMIT):
        # 아무도 못 맞추면 누구도 획득하지 못한다.
        if (ryan_scores[i], apeach_scores[i])==(0,0):
            continue
            
        elif ryan_scores[i]>apeach_scores[i]:
            champion_score+=(10-i)
        else:
            challenger_score+=(10-i)
    
    return champion_score-challenger_score

# step : 기저조건 도달용 변수 (또는 info index). default 0
# arrow : 남은 화살 횟수. default n 
# result : 재귀로 담을 결과 리스트. default [0 for i in range(11)]
def get_score(step:int,arrow:int,result:list,info:list):
    global LIMIT,max_scores_list,max_score
    
    # 남은 화살이 없다면, 기저 조건 도달
    if step==LIMIT or arrow==0:
        # 얻어낸 최종 결과로 차이를 비교한다.
        difference=calculate_difference(result,info)
        
        # 음수 또는 0이면 더 볼 필요 없이 리턴
        if difference<=0:
            return
        
        # 최고 점수를 갱신했다면, 기존 리스트는 필요 없다. 딥 카피로 해야 참조에 의해 변경이 되지 않는다.
        if difference>max_score:
            max_score=difference
            max_scores_list=list(result)
            
        elif difference == max_score:
            # 제일 뒤 점수인 0점부터 시작해서 거꾸로 확인
            for i in range(LIMIT):
                if result[-i]>max_scores_list[-i]:
                    max_scores_list=list(result)
                    break
                elif result[-i]<max_scores_list[-i]:
                    break
        return
    
    
    else:
        # 라이언이 k점에서 점수를 얻는 방법은, 어피치보다 1개 더 쏘는 것이다. 
        # 그 이하는 아무런 효력이 없다.
        
        apeach_score=info[step]
        
        # range : 0 ~ apeach의 개수 + 1
        for count in range(apeach_score+2):
            if count<=arrow:
                # 남은 화살의 총량 이하라면, 해당 수 만큼 쏠 수 있다.
                result[step]=count
                # 쏜 화살 만큼 줄이고, 해당 분기로 더 깊이 들어간다. 
                get_score(step+1,arrow-count,result,info)
                # 분기를 나오고 나선, 다른 분기도 살펴봐야 하므로 초기화한다.
                result[step]=0
        
def solution(n, info):
    answer = []
    
    get_score(0,n,[0 for i in range(LIMIT)], info)
    
    # 라이언이 우승할 수 없을 경우 해당
    if len(max_scores_list)==0:
        return [-1]
    return max_scores_list

예제 24, 25만 틀릴 경우

다음과 같이 재귀 구조를 짜면 24,25 예제가 틀린 걸로 나온다.

def get_score(step:int,arrow:int,result:list,info:list):
    # 남은 화살이 없다면, 기저 조건 도달
    if arrow==0:
    	do something()
        return
    if step==LIMIT:
    	# do nothing
    	return
    
    else:
    	do some recursive logic()
        

어찌보면 당연한 이유인게, step==LIMIT 일 때도 기저조건 도달 후에 calculate_difference()를 호출해야 하기 때문이다.

따라서 step>=LIMIT or arrow<=0으로 기저 조건을 설정하자.

느낀 점

작년 9월 카카오 공채에서 맞춘 문제였다. 이 문제까지 풀어서 4개 반으로 1차를 통과했었다. 그런데 6개월 정도 지나고 나서 푸니까 42.9/100.0점이 나오더라.
그 때의 기지로 푼게 용했다. 복습 꼭 하자.

참고 자료

https://yensr.tistory.com/m/24