SWEA 4466 파이썬 문제풀이(최대 성적표 만들기)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWOUfCJ6qVMDFAWg 

SW Expert Academy

 

---

이 문제의 풀이법은 3가지가 있다. 첫번째는 이 문제가 요구하는 방식이다. 우선 내림차순으로 점수들을 정렬한다음 K개를 뽑으면 된다. 그러면 가장 큰 점수이다. 

그러나 이러한 문제는 기본적으로 재귀로도 풀 수 있다. N개중 K를 뽑는 문제이기 때문이다. 하지만 위 문제에서 재귀로 풀면 시간초과가 발생한다. 또한 itertools.permutations 로도 풀 수 있다. 파이썬 조합라이브러리이다. 

 

1. 내림차순 정렬 방식

T = int(input())

for order in range(1, T + 1):
    N, K = map(int, input().split())
    total = list(map(int, input().split()))
    total.sort(reverse=True)
    result = 0
    for i in range(K):
        result += total[i]

    print(f'#{order} {result}')

 

2. 재귀

T = int(input())


def solution(depth, step):
    global result

    if depth == K:
        if result < sum(sum_):
            result = sum(sum_)
            return
        else:
            return

    for i in range(step, N):
        sum_.append(total[i])
        solution(depth + 1, i + 1)
        sum_.pop()


for order in range(1, T + 1):
    N, K = map(int, input().split())
    total = list(map(int, input().split()))
    sum_ = []
    result = 0
    solution(0, 0)
    print(f'#{order} {result}')

 

3. 조합라이브러리 이용

import itertools

T = int(input())

for order in range(1, T + 1):
    N, K = map(int, input().split())
    total = list(map(int, input().split()))
    total.sort(reverse=True)
    result = 0
    for i in itertools.permutations(total, K):
        if result < sum(i):
            result = sum(i)

    print(f'#{order} {result}')