[프로그래머즈/Python] 2022 블라인드 카카오 - 양궁대회

문제

2022 KAKAO BLIND RECRUITMENT의 양궁대회 문제입니다. 

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

프로그래머스

 

코드

def solution(n, info):
    def get_score_diff(ryan, apeach):
        sr, sa = 0, 0
        for i in range(11):
            if ryan[i] > apeach[i]:   
                sr += (10 - i)
            elif apeach[i] > 0:       
                sa += (10 - i)
        return sr - sa

    def is_low(new_arr, old_arr):
        for i in range(10, -1, -1):
            if new_arr[i] > old_arr[i]:
                return True
            elif new_arr[i] < old_arr[i]:
                return False
        return False  

    best_diff = 0
    best_arr = [-1]

    def dfs(index, arrows_left, ryan):
        nonlocal best_diff, best_arr
        
        if index == 11:
            diff = get_score_diff(ryan, info)
            if diff > best_diff:
                best_diff = diff
                best_arr = ryan[:]
            elif diff == best_diff and diff > 0:
                if is_low(ryan, best_arr):
                    best_arr = ryan[:]
            return
        
        for x in range(arrows_left + 1):
            ryan[index] = x
            dfs(index + 1, arrows_left - x, ryan)
            ryan[index] = 0  

    ryan_arr = [0]*11
    dfs(0, n, ryan_arr)

    if best_diff <= 0:
        return [-1]
    else:
        return best_arr

 

라이언이 어피치를 큰 점수차로 이기게 도와줘야합니다. 

 

문제 접근 

처음에는 점수에 맞춰야하는 화살을 나눠서 스코어를 만들어 그리디로 접근하려 했지만 고려해야하는 경우의 수가 매우 많아 다른 방법으로 접근했습니다. 

 

사용하는 화살의 수가 최대 10개로 매우 적기때문에 전수조사를 하는 방법을 사용할 수 있습니다.  

 

DFS를 이용한 전수조사 풀이입니다. 

 

DFS내에서는 주어진 n만큼의 전수조사를 진행합니다. 스코어는 0부터 10까지 11이 있으므로 index가 11까지 진행되면 점수 분배를 체크합니다. 

[점수 분배 체크] 

get_score_diff를 통해 라이언 점수 - 어피치 점수를 가져옵니다. 

이러면 경우의수가 3가지입니다. 

1. 라이언이 어피치를 임시최적해보다 더 큰 점수차로 이기는 경우

2. 라이언이 어피치를 임시최적해만큼의 점수차로 이기는 경우

3. 라이언이 임시최적해보다 작은 점수차로 이기거나 지는 경우 

 

3번은 무시하고 1번과 2번만 고려합니다. 

1번의 경우 최적해를 바로 적용해줍니다. 

2번의 경우 is_low 함수를 통해

이 조건을 달성할 수 있습니다.