문제 이해

N개 자연수 중에 K개를 고를 것이다.

이 때 1개 값에 대한 점수는 "선택한 자연수 - 해당 자연수 왼쪽에 선택된 숫자의 개수" 이다.

이렇게 구한 K개 점수를 모두 더한 값을 전체 점수라고 한다.

전체 점수의 최댓값을 구하는 문제이다.

---

문제 풀이

참 어려워 보이는 문제이면서 생각을 전환만 하면 쉬운 문제이다.

우리에게 중요한 것은 Array의 값이라기보다는 "선택한 자연수 왼쪽에 존재하는 선택된 숫자의 개수"이다.

그런데 생각해보면, 이 값은 무조건 고정되어 있음을 알 수 있다.

첫 번째 선택한 값 왼쪽 개수는 0, 두 번째 선택한 값의 왼쪽 개수는 1,..., N번째 선택한 값의 왼쪽 개수는 (N-1),...이 될 것이다.

즉, K번째 선택한 값까지의 왼쪽 개수를 모두 더하면 0 + 1 + ... + (K-1) = K*(K-1)/2로 값이 고정되어 있다.

따라서, 우리가 구해야 할 값은 주어진 배열 중 가장 큰 K개의 숫자를 골라 더하고, 이 값에 K*(K-1)/2를 빼주기만 하면 그 값이 곧 전체 점수의 최댓값이 될 것이다.

---

코드

JAVA

import java.io.*;
import java.util.*;

public class Main {
	static StringBuilder sb = new StringBuilder();

	
	public static void main(String[] args) {
		FastReader sc = new FastReader();
		
		int N = sc.nextInt();
		int K = sc.nextInt();
		Integer[] arr = new Integer[N];
		for(int i =0;i<N;i++) {
			arr[i] = sc.nextInt();
		}
		
		int minus = (K-1)*K / 2;
		
		Arrays.sort(arr, Collections.reverseOrder());
        // arr를 내림차순으로 정렬
		
		int answer = 0;
		for(int i =0;i<K;i++) {
        // 정렬한 배열을 앞에서부터 K개를 뽑아 더해줌
			answer += arr[i];
		}
		
		System.out.println(answer - minus);
		
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

Python

[N,K] = list(map(int,input().split()))
arr = list(map(int, input().split()))

minus = (K-1)*K / 2

arr = sorted(arr, reverse=True)

answer = 0

for i in range(K):
    answer += arr[i]

print(int(answer - minus))

---

결과