[프로그래머스] 양궁대회 (파이썬)

난이도 : LV2

문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/92342

문제해결

• 매 점수 마다 라이언은 0발을 쏴서 점수를 포기하거나 어피치보다 한발 더 많이 쏴서 최소의 화살 개수로 점수를 획득해야한다.
• DFS를 사용해서 10점부터 0점까지 점수를 획득, 포기 했을 경우 전체 탐색.
• 이때 만약 화살이 남았을 시, 남은 화살은 전부 0점에 털어야한다.
• 정답이 여러개일 경우, 낮은 점수를 많이 쏜 과녁을 리턴해야 하는데,
• 과녁 배열을 문자열로 합치고 뒤집은 다음 숫자화 하여 가장 큰수가 되면 된다.

소스코드

ans = []
maxVal = 0
def getScore(board,info):
    ap_sc = li_sc = 0    
    for i in range(len(info)):
        if board[i] > info[i]:
            li_sc += (10 - i)
        elif board[i] == info[i]:
            continue
        else:
            ap_sc += (10-i)
    
    if li_sc > ap_sc:
        return (True,li_sc)
    
    return (False,li_sc)
    

def dfs(idx, lion_board, rest_arrow, info):
    global maxVal
    if idx == len(lion_board) or rest_arrow == 0:
        if rest_arrow > 0:
            lion_board[idx-1] = rest_arrow
        result = getScore(lion_board, info)[0]
        li_sc = getScore(lion_board, info)[1]
        
        if result and li_sc >= maxVal:            
            maxVal = li_sc
            ans.append((lion_board[:], li_sc))
        lion_board[idx-1] = 0
        return
    
    if info[idx] < rest_arrow:
        lion_board[idx] = info[idx] + 1
        dfs(idx+1, lion_board, rest_arrow-lion_board[idx], info)
        lion_board[idx] = 0
        
    dfs(idx+1, lion_board, rest_arrow, info)
    
def solution(n, info):
    lion = [0] * 11    
    dfs(0,lion,n,info)
    new_ans = []
    for i in ans:
        if i[1] == maxVal:
            new_ans.append(i)
    
    if len(new_ans) == 0:
        return [-1]
    elif len(new_ans) == 1:
        return new_ans[0][0]
    else:
        re = 0
        for i in new_ans:
            if int("".join(i[0])) > re:
                a = i[0]
                re = int("".join(i[0]))

        return a