[실버 4] 백준 29767 - 점수를 최대로 (파이썬)

https://www.acmicpc.net/problem/29767

풀이

길이가 N인 정수 수열 A가 주어지며, 누적합(A[0]부터 A[i]까지의 합)을 구해 전체 N개의 누적합 중 K개를 선택해서 합을 최대로 만들어야한다.

N, K = map(int, input().split())
A = list(map(int, input().split()))

N은 원소 개수, K는 선택할 누적합 개수를 입력 받는다.

psum = [0] * N
psum[0] = A[0]

for i in range(1, N):
    psum[i] = psum[i - 1] + A[i]

psum[i]는 A[0] + A[1] + … + A[i]를 의미하며, 즉, 누적합 배열을 만든다.

psum.sort(reverse=True)
print(sum(psum[:K]))

누적합 배열을 내림차순 정렬한 뒤, 상위 K개의 값을 선택하여 더한 결과를 출력한다.

결국 이 문제 풀이의 아이디어는 누적합은 앞에서부터의 합이므로 psum[i]는 i + 1개 원소의 부분합니다.

점수를 최대로 하려면 가장 큰 누적합들만 선택하면 되고, 따라서 누적합 배열을 정렬해 상위 K개만 골라서 더하면 해결 할 수 있는 문제이다.

코드

# 백준 29767 - 점수를 최대로
# 분류 : 누적합 + 그리디

N, K = map(int, input().split())
A = list(map(int, input().split()))

psum = [0] * N
psum[0] = A[0]

for i in range(1, N) :
    psum[i] = psum[i - 1] + A[i]

psum.sort(reverse=True)
print(sum(psum[:K]))