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

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

프로그래머스

 

💬 라이언이 화살을 쏠 수 있는 경우를 DFS로 구한 후, 라이언과 어피치의 점수차를 계산한다.

💬 풀다가 막혀서 고민하다 카카오의 해설을 참고했고, 라이언이 한 과녁에 쏴볼 수 있는 화살의 제한을 (0 ~ 어피치가 쏜 화살 +1)로 두어야 시간초과가 나지 않는다는 한다는 팁을 얻었다.

💬 중간에 계속 answer의 값이 0으로 가득차 나오는 오류가 있었다...😭 계속 디버깅 해봐도 이유를 모르겠어서 구글링 해보았는데 list(배열) 이 방식으로 해결하신 분이 있었다. 왜 저렇게 하면 되는 거지,,,ㅠㅜ

➡ 이유를 알았다! 원래는 max_list = lion으로 넣었는데, lion 배열은 DFS 함수에서 추후 [0, 0, 0, 0, ...] 으로 초기화 된다. 그래서 혹시 얕은 복사 문제일까 싶어 deepcopy를 써주었는데, 해결되었다!🤗

 

from copy import deepcopy

max_gap = 0
max_list = []

def cal_score(apeach, lion):
    global max_gap, max_list
    apeach_score = 0
    lion_score = 0
    for idx in range(11):
        if apeach[idx] == 0 and lion[idx] == 0:
            continue
        if apeach[idx] >= lion[idx]:
            apeach_score += 10-idx
        elif apeach[idx] < lion[idx]:
            lion_score += 10-idx

    if lion_score > apeach_score:
        gap = lion_score - apeach_score
        if gap > max_gap:
            max_gap = gap
            max_list = deepcopy(lion)

        elif gap == max_gap:
            for idx in range(10, -1, -1):
                if lion[idx] > max_list[idx]:
                    max_list = deepcopy(lion)
                    break
                elif lion[idx] < max_list[idx]:
                    break

def DFS(idx, lion, shot, apeach):
    if shot == 0:
        cal_score(apeach, lion)
        return
    if idx == 11:
        return
    a_score = apeach[idx]
    for num in range(a_score+2):
        if shot >= num:
            lion[idx] = num
            DFS(idx+1, lion, shot-num, apeach)
            lion[idx] = 0

def solution(n, info):
    global max_list
    temp = [0 for _ in range(11)]
    DFS(0, temp, n, info)

    if max_list:
        return max_list
    else:
        return [-1]