백준_29767_점수를 최대로 (python)

와우와우와우와우와우 진짜 맛도리 문제였다.

처음에는 조합을 떠올렸으나 입력 크기를 보고 그리디를 생각했다. 하지만 그리디로 생각하기에는 말이 안되는 부분들이 많아서 dp가 아닌가 싶었다. 그런데 또 dp로 풀자니 안 돼서 알고리즘 분류를 봤다.

그리디, 누적합, 정렬이 있는 것을 보고 더 헷갈렸다.

 

정렬을 처음부터 하는 것은 문제에 어긋나는 것이기 때문에 안되고

그리디는 처음에 생각했던 것처럼 말이 안 됐고

남은 것은 누적합인데 평소에 ps에서 누적합의 빈도가 낮긴 했지만 그렇다고 모르는 알고리즘을 아니었지만 도대체 누적합으로도 어떻게 풀라는 것인가 k명이 교실을 선택해야 하는데 흠......

 

교실 점수에 * 횟수를 막 그리디적으로 해보다가  문제에서 시키는 대로 그냥 한 명 한 명 교실을 택해서 앞으로 건너가는 시뮬레이션을 그려봤다.

그러다가 누적 합이 보였고

그러다가 높은 점수만 택해야 하는 그리디가 보였고 높은 점수만 택하기 위해서 정렬을 사용해야 했다. 

 

결국 알고리즘 분류에서 말하던 알고리즘들을 다 사용해서 문제를 풀었다. 쉬운 문제였지만 요즘에 ps 침체기가 와서 풀기 쉽지 않았다.

# 코드

import sys
input = sys.stdin.readline
n,k = map(int,input().split())
data = list(map(int,input().split()))
dp = [0] * n
dp[0] = data[0]
for i in range(1,n):
	dp[i] = dp[i-1] + data[i]
dp.sort(reverse=True)
print(sum(dp[:k]))

 

 

# 회고

문제에서 k개 택하라고 하고 알고리즘 분류에서는 누적합이라고 하니 두개를 어떻게 섞어야 하는지 에서 혼동이 왔었지만  이럴 때는 하나하나 나눠서 시도해 보면 될 것 같다. 그래도 안 되면 문제 자체를 시뮬레이션을 돌려보자!!