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

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

코딩테스트 연습 - 양궁대회

 

이 문제를 작년에 2022 KAKAO BLIND RECRUITMEMT 에서 풀었을 때는 DFS로 접근하였다.

이번에는 product 를 이용하여 경우의 수 2,048개를 구해놓고 조건에 맞으면 해당 점수의 차이와 라이언의 기록을 기억하여 점수가 크거나, 점수가 같을 때는 낮은 점수의 과녁을 많이 맞힌 기록을 새로이 기억하여 마지막으로 기억하는 라이언의 기록을 반환한다.

 

라이언이 어피치보다 과녁의 점수 별로 높지 않으면 어피치가 점수를 가져가거나 0점이기 때문에(모두 0발을 맞힌 경우) 라이언이 점수를 가져가는 경우를 1, 그렇지 않은 경우를 0으로 2,048개의 경우의 수가 나온다.

 

1인 경우는 라이언이 점수를 가져가는 경우로 info[j] + 1발을 맞혀야 한다.

0인 경우는 라이언이 점수를 가져가지 않는 경우로 0발을 맞혀야 한다.

n에서 라이언이 맞힌 화살의 수를 뺐을 때 0보다 같거나 커야 하고 점수 차이가 가장 컸을 때 라이언이 맞힌 화살의 수가 n보다 작다면 낮은 점수의 과녁을 많이 맞힌 기록을 반환 해야하기 때문에 0점짜리를 남은 화살의 수만큼 맞힌 걸로 하면 된다.

 

from itertools import product

def solution(n, info):
    answer = [0] * 11
    m = 0
    
    for i in product([0, 1], repeat = 11):
        k = n
        temp = []
        score = 0
        
        for j in range(11):
            if i[j] == 1:
                temp.append(info[j] + 1)
                k -= (info[j] + 1)
                score += (10 - j)
            else:
                temp.append(0)
                
                if info[j] != 0:
                    score -= (10 - j)
                             
        if k >= 0 and m <= score:
            if m == score:
                for s in range(10, -1, -1):
                    if answer[s] != temp[s]:
                        if answer[s] < temp[s]:
                            answer = temp

                        break
            else:
                m = score
                answer = temp
            
    if m == 0:
        answer = [-1] 
    else:
        if sum(answer) < n:
            answer[10] += (n - sum(answer))
    
    return answer

print(solution(5, [2, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0])) # [0, 2, 2, 0, 1, 0, 0, 0, 0, 0, 0]