[프로그래머스] 양궁 대회 (Lv 2)

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

프로그래머스

 

보기보다는 매우 간단한 문제이다. 0점을 제외하고 한 발 더 쏘거나, 아예 안 쏘거나 그리디한 케이스만 따지면 된다.
남는 화살은 모두 0발로 간다. 어차피 0 안보내도 아예 질거라면 무조건 지고, 최적의 케이스는 저기 안에서만 나온다.

저 케이스를 1점~10점 모두 순차적으로 따져줘야 하므로 DFS가 가장 자연스럽다.

아, 점수 차가 동일할 케이스가 여러 개 나올 수도 있다. 이때 예외처리를 위해 정렬 잊지 말자. 이거 빼먹어서 두 번 실패함.

win_flag = False
answer = []
max_diff = 0

def peach_lion_score(peach, lion):
    peach_score = 0
    lion_score = 0
    for i in range(0, 10):
        cur_score = 10 - i
        if peach[i] == 0 and lion[i] == 0:
            pass
        else:
            if peach[i] >= lion[i]:
                peach_score += cur_score
            else:
                lion_score += cur_score
    return [peach_score, lion_score]

def dfs(lion_left_arrow, cur_pos, peach, lion):
    global win_flag
    global answer
    global max_diff
    
    if len(lion) == 10:
        # 10개를 다 쏘고 승패 비교
        result = peach_lion_score(peach, lion)
        if result[0] < result[1]:
            # 일단 이겼다면 승리는 가능하다.
            win_flag = True
            # 점수 차를 비교한다.
            if result[1] - result[0] > max_diff:
                max_diff = result[1] - result[0]
                answer = [lion.copy()]
                answer[0].append(lion_left_arrow)
            # 점수 차가 동일할 때 조건부 출력을 위한 추가 처리
            elif result[1] - result[0] == max_diff:
                answer.append(lion.copy())
                answer[-1].append(lion_left_arrow)
    else:
        # 어피치 보다 한발만 더 그리디하게 쏘자. 두 발 이상 이기는건 의미 없다.
        if lion_left_arrow >= peach[cur_pos] + 1:
            lion.append(peach[cur_pos] + 1)
            dfs(lion_left_arrow - (peach[cur_pos] + 1), cur_pos + 1,
               peach, lion)
            lion.pop()
        # 그걸 쏴서 이길 수 없을 때는 그 점수는 0발로 간다.
        lion.append(0)
        dfs(lion_left_arrow, cur_pos+1, peach, lion)
        lion.pop()
        
def solution(n, info):
    lion = []
    global max_diff
    global answer
    
    dfs(n, 0, info, lion)
    # 응 절대 어피치 못이김~
    if win_flag == False:
        return [-1]
    # 낮은거 가장 많이 쏘게
    answer.sort(key = lambda x : x[::-1], reverse = True)
    return answer[0]