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

2022 KAKAO BLIND RECRUITMENT - 92342. 양궁대회

[Lv. 2]

 

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

프로그래머스

 

풀이

처음 보았을 때는, Greedy하게 접근해야 할 지, DP로 접근해야 할 지.. 고민이였으나,

정확성 테스트로 제한 시간이 10초, 성능 테스트가 없었으며,

배열의 길이도 11이므로 2^11 = 2048가지 정도의 경우의 수를 다 따져보아도, TLE가 나지 않을 것이라 생각.

따라서, Brute-Force로 풀이했다.

 

과녁 상의 어떤 한 점수를 얻을 지 말 지에 따라, 2^11가지의 경우의 수가 나옴.

(10점을 얻을 것인지, 9점을 얻을 것인지...~)

그리고, 남은 화살 개수에 따라 불가능하다면 pass, 가능하다면 최고점과 비교해가며, 최고점+가장 낮은 점수에 화살을 많이 쏜 경우를 저장.

 

from itertools import product

def solution(n, info):
    A = list(product([True, False], repeat=11))

    max_score = 0
    max_list = [0,0,0,0,0,0,0,0,0,0,0]

    for a in A:
        num = n
        for i in range(11):
            if a[i]:
                num -= info[i]+1

        if num < 0:
            continue

        # 점수차 계산
        lion = 0
        apeach = 0
        for i in range(11):
            if a[i]:
                lion += 10-i
            elif info[i] > 0:
                apeach += 10-i

        if max_score < lion - apeach:
            max_score = lion - apeach
            temp = []
            for i in range(11):
                if a[i]:
                    temp.append(info[i]+1)
                else:
                    temp.append(0)

            temp[10] += num
            max_list = temp

        elif max_score == lion - apeach:
            temp = []
            for i in range(11):
                if a[i]:
                    temp.append(info[i]+1)
                else:
                    temp.append(0)

            temp[10] += num

            # 더 낮은 점수가 높다면 바꿔치기
            for i in range(10, -1, -1):
                if temp[i] > max_list[i]:
                    max_list = temp
                    break
                elif temp[i] < max_list[i]:
                    break

    if max_score == 0:
        max_list = [-1]
    
    return max_list