프로그래머스[ LV2 | Python ] 양궁 대회

문제

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

풀이

주어진 조건을 통해 이를 어떻게 그래프로써 생각할 수 있을까 고민하다가, 끝내 해결책을 찾아내지 못해 다른 분의 블로그를 통해 해결했고 이를 기억속에 남기기위해 해결 과정은 주석으로 달아놨다.

from copy import deepcopy
max_val, max_target = 0, []
def solution(n, info):
    def dfs(ascore, rscore, r_arrow, score, target):
        global max_val, max_target
        if r_arrow > n:#r_arrow는 라이언이 쏘는 화살의 수
            return
        if score > 10:#모든 점수를 다 노렸으면
            diff = rscore - ascore#차이를 구하고
            if diff > max_val:
                target[10] = n - r_arrow#라이언이 가장 큰 점수차이로 우승할 수 있는 방법이 여러 가지 일 경우, 가장 낮은 점수를 더 많이 맞힌 경우를 return 하는 조건
                max_target = target
                max_val = diff
            return
        if r_arrow < n:#n 보다 화살을 덜 쐈으면
            target2 = deepcopy(target)
            target2[10-score] = info[10-score] + 1#끝에서부터 어피치보다 한발 더쏜다. 
            dfs(ascore, rscore+score, r_arrow+info[10-score]+1, score+1, target2)#정보를 그대로 넘겨주되 score에 현재 쏘려는 점수를 높혀주고 라이언의 현재까지의 점수를 갱신, 어피치의 화살보다 1개 더 많은 수의 화살을 갱신
            
        target1 = deepcopy(target)
        
        if info[10-score] > 0:#위 조건에 모두 걸리지 않고 어피치가 라이언이 지금 쏘려는 점수에 한발 이상 맞춘경우
            dfs(ascore+score, rscore, r_arrow, score+1, target1)#어피치에게 그 점수를 주고 다른 점수를 노림
        else:#어피치가 라이언이 지금 쏘려는 점수에 못맞춘 경우
            dfs(ascore, rscore, r_arrow, score+1, target1)#다음 점수를 노림 
            
    dfs(0, 0, 0, 0, [0]*11)
    return max_target if max_target else [-1]

생각 & 정리

안그래도 성가셔하는 구현과 DFS가 합쳐져서 곤란스러웠다.
주어진 info변수를 그래프와 연관지어 생각하는데에 어려움이 있었고, 따라서 이를 어떻게 탐색해야하는지도 의문스러웠다.
작성하신 분의 코드를 보고 어렵다는 생각이 들어도 차근차근 하나씩 구현해나가는게 중요하다는 생각이 들었다.

Reference.

https://velog.io/@jadenkim5179/프로그래머스-양궁대회