[프로그래머스 | Lv2] 양궁대회 (Python) - 2022 KAKAO BLIND RECRUITMENT

 

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

프로그래머스

 

BFS를 이용하여 풀었다.

 

화살을 쏠 수 있는 경우 (남은 화살이 존재)

10점부터 차례대로 화살을 쏜다.

쏠 수 있는 화살은 어피치보다 1발 더 쏘기 or 0발 쏘기이다.

deque에 쏠 수 있는 화살 리스트를 모두 갱신하여 저장한다.

 

더이상 쏠 화살이 없는 경우

10~1점까지 모든 화살을 다 쐈고, 남은 화살이 존재할 경우 0점에 남은 화살을 몰아준다.

라이언과 어피치의 점수를 계산하여 둘의 점수차가 가장 큰 값으로 정답을 갱신한다.

최댓값이 여러개일 경우, answer에 해당 리스트를 추가해준다.

 

answer이 빈 값이 아닐 경우

원소를 거꾸로 정렬하여 가장 마지막 리스트를 리턴한다. (가장 낮은 점수를 더 맞힌 리스트)

answer이 빈 값인 경우

[-1]을 리턴해준다. (라이언이 어피치를 이길 수 있는 경우가 존재하지 않는다.)

 

# 프로그래머스 92342: 양궁대회 (2022 KAKAO BLIND RECRUITMENT)

from collections import deque 

def solution(n, info):
    answer = []
    res = 1 # 비기는 경우 고려하여 1로 초기화
    queue = deque()
    queue.append([0, [0] * 11]) # [pos, score]
    
    while queue:
        pos, q = queue.pop()
        
        if sum(q) == n or (sum(q) < n and pos == 9): # 10~1점까지 모든 화살을 다 쏜 경우
            if (sum(q)) < n:
                q[10] = n - sum(q) # 0점에 남은 화살 몰아주기

            ryan = 0
            apeach = 0
            for i in range(10): # 점수 계산 (0점은 계산할 필요 X)
                if q[i] > 0:
                    ryan += 10 - i
                elif info[i] > 0:
                    apeach += 10 - i

            if res < ryan-apeach: # 최댓값 갱신
                answer = [q]
                res = ryan - apeach
            elif res == ryan-apeach:
                answer.append(q)

        elif sum(q) < n: # 남은 화살이 존재할 경우
            q1 = q.copy()
            q2 = q.copy()
            
            q1[pos] = 0
            q2[pos] = info[pos] + 1
            pos += 1
            
            queue.append([pos, q1])
            queue.append([pos, q2])

    if answer:
        answer.sort(key = lambda x : x[::-1]) # 원소를 거꾸로 정렬
        return answer[-1]
    
    return [-1]

 

풀기 너무 힘든 문제였다,,,, 분발하자 🙌🥲