양궁대회 (Level 2)

문제

 

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

프로그래머스

 

내 풀이

 

백트래킹을 사용해서 문제를 풀었다.

 

함수는 두 개 만들었는데, 첫 번째 함수는 어피치와 라이언의 점수 배열을 보고 점수가 몇 점인지 구하는 함수이고, 두 번째 함수는 dfs를 사용한 백트래킹 함수이다.

 

idx를 0부터 시작해서 하나씩 증가시키면서 재귀 함수가 돌아가도록 설계하였다.

 

idx가 11일 때, 즉 라이언의 배열에 숫자를 모두 채웠을 때 어피치와 라이언의 점수를 cal 함수를 통해 구하고, 점수 차가 최대인지 구하였다. 이때 max_num을 계속 갱신하였다. 

(라이언 점수 - 어피치 점수)가 최대이면 answer에 만들었던 라이언 배열을 추가하고, 이전에 갱신된 max_num과 동일한 값이면 answer에 추가하는 방식으로 구현하였다.

 

idx가 11인데 sum(lion) < n인 경우는 라이언이 남은 화살을 모두 과녁의 0점 배점인 곳에 맞혔다고 보면 된다.

 

라이언 배열의 현재 인덱스(idx)의 숫자가 어피치보다 1 큰 경우와 라이언 배열의 현재 인덱스(idx)의 숫자가 0인 경우를 구현하기 위해 백트래킹을 선택하였다. 이 경우일 때 재귀 함수를 사용하면 된다. 

백트래킹이기 때문에 재귀가 끝나면 반드시 pop을 해야 한다.

 

dfs 함수 구현 후, answer의 원소 개수가 2개 이상인 경우가 있기 때문에 answer 배열을 정렬해주어야 한다. 정렬 기준은 '가장 낮은 점수를 더 많이 맞힌 경우'라고 문제에 나와있다. 

 

max_num = -1
answer = []
    
def solution(n, info):

    def cal(appeach, lion):
        a_score, l_score = 0, 0
        for i in range(11):
            if appeach[i] == lion[i] == 0: continue
            elif appeach[i] > lion[i]:
                a_score += 10 - i
            else:
                l_score += 10 - i
        return a_score, l_score
    
    def dfs(lion, idx):
        global max_num, answer
        
        if idx == 11:
            a, l = 0, 0
            if sum(lion) == n:
                a, l = cal(info, lion)
            elif sum(lion) < n:
                lion[-1] += (n - sum(lion))
                a, l = cal(info, lion)
            else:
                return
            if a < l:
                if max_num < (l-a):
                    max_num = (l-a)
                    answer = [lion[:]]
                elif max_num == (l-a):
                    answer.append(lion[:])
            return
        
        lion.append(info[idx]+1)
        dfs(lion, idx+1)
        lion.pop()
        
        lion.append(0)
        dfs(lion, idx+1)
        lion.pop()
    
    dfs([], 0)
    if not answer: return [-1]

    answer.sort(key=lambda x: x[::-1], reverse=True)    
    return answer[0]

 

총평

푸는 데 좀 오래 걸렸다.

어쩌겠어. 나는 아직 하수인걸!

더 빠르게, 더 깔끔하게 풀 수 있도록 계속 연습해야겠다.