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

💡 문제 해결 아이디어

내가 생각한 아이디어

• 기본 : 효율적으로 화살을 쏘기 위해서는 (어피치+1)만큼 맞추거나 안맞춰야겠다!
• 1트 : 어피치보다 많이 쏘면 어피치는 점수를 못 얻고 라이언은 점수를 얻으니 더 큰 점수차를 가져다 주네?? 그럼 효율성으로 가야겠ㄷ...
• 2트 : Greedy가 아니라 knapsack 문제네 ㅎㅎ... 그러면 백트래킹으ㄹ...
• 3트 : 이유는 모르겠지만 knapsack이 안되넹... 그냥 완전탐색으로 해야겠네 😭
• BFS를 선택한 이유 : 쏠 수 있을 때 쏘는 경우를 먼저 queue에 append하고 쏘지 않는 경우를 나중에 append한다면, 결국 마지막에 찾은 answer이 무조건 낮은 점수를 더 많이 맞춘 경우일 것이기 때문이다.

💻 작성된 코드(수정)

def solution(n, info):
	# 어피치의 총 점수 계산
    apeach = sum([10-i for i in range(10) if info[i]])
    # 과녁의 각 점수별 실질적으로 얻어지는 점수
    score = [(10-i)*2 if info[i] else 10-i for i in range(10)]
    # BFS를 위한 queue. 10점을 쏘지 않은 경우 기본 추가
    queue = [[0]]
    answer = []
    # 10점을 쏠 수 있는 경우, 쏜 경우를 queue에 추가
    if n >= info[0]+1:
        queue.append([info[0]+1])
        
    while queue:
        recent = queue.pop(0)
        # 주어진 화살을 다 쐈거나, 10~1점까지 다 쏜 경우
        if sum(recent) == n or len(recent) == 10:
            new = sum([score[i] for i in range(len(recent)) if recent[i]])
            old = sum([score[i] for i in range(len(answer)) if answer[i]])
            # apeach보다 많은 점수를, 그리고 기존 answer 이상의 점수를 얻었다면 update
            if new > apeach and new >= old:
                answer = recent
        # 아직 덜 쐈는데, 이번 점수에 (어피치+1)을 쏠 수 있다면
        elif sum(recent)+info[len(recent)]+1 <= n:
        	# 쏜 경우, 안 쏜 경우 모두 queue에 append
            queue.append(recent + [info[len(recent)]+1])
            queue.append(recent + [0])
        # 아직 덜 쐈는데, 쏠 화살이 안 남아있다면, 안 쏜 경우만 append
        else :
            queue.append(recent + [0])
    # apeach보다 많은 점수를 낼 수 없다면, [-1] return
    if not answer:
        return [-1]
    # 그렇지 않다면, [answer + 남은 점수 안쏘고 + 0점에 다 쏘기] return
    return answer + [0]*(10 - len(answer)) + [n-sum(answer)]