Programmers - 양궁 대회

문제 링크

10점 ~ 0점까지 각 점수를 획득하는 경우와 그렇지 않은 경우를 모두 탐색한다.

search(index,remain_arrows,ryan,apeach)

• 모든 경우의 수를 재귀로 탐색
• 각 index의 점수를 획득하는 경우와 획득하지 않는 경우를 탐색
• 화살이 남은채로 마지막 인덱스(0점)에 도달한 경우 남은 화살을 다 쏜다.

process() : search에서 탐색이 끝난 경우 점수를 계산하는 로직

get_higher_priority() : 동점인 경우 낮은점수를 많이 쏜 정보를 return

max_score = -987654321
max_shot_info = []


def process(ryan, apeach):
    global max_score
    global max_shot_info

    r_score = 0
    a_score = 0
    for i in range(11):
        if ryan[i] == 0 and apeach[i] == 0:
            continue

        if ryan[i] > apeach[i]:
            r_score += 10-i
        else:
            a_score += 10-i

    diff = r_score - a_score
    if diff > max_score:
        max_score = diff
        max_shot_info = ryan
        return

    if diff == max_score:
        max_shot_info = get_higher_priority(ryan, max_shot_info)

# 낮은점수에 많이 쏜 경우를 return


def get_higher_priority(arr1, arr2):
    for i in range(10, -1, -1):
        if arr1[i] > arr2[i]:
            return arr1
        if arr1[i] < arr2[i]:
            return arr2

# 얻는 경우와 안얻는 경우


def search(index, remain_arrows, ryan, apeach):
    # base case
    copied = ryan[:]
    if index == 10:
        copied[10] += remain_arrows
        process(copied, apeach)
        return
    if remain_arrows == 0:
        process(copied, apeach)
        return

    # index번 점수 얻는 경우
    if remain_arrows > apeach[index]:
        copied[index] = apeach[index] + 1
        search(index+1, remain_arrows - copied[index], copied, apeach)

    # 점수 안 얻는 경우
    search(index+1, remain_arrows, ryan, apeach)


def solution(n, info):

    ryan = [0 for _ in range(11)]
    search(0, n, ryan, info)

    # print(max_score, max_shot_info)

    if max_score <= 0:
        return [-1]

    return max_shot_info