백준 20186 - 수 고르기 (자바 - 그리디)

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

20186번: 수 고르기

 

* 문제 요약

N 개의 자연수가 좌우로 배열되어 있다. 여러분은 이 중 K 개를 골라야 한다. 고를 때는 K 개 모두를 한번에 골라야 한다.

여러분이 고른 수 각각에 대해서 그 수의 점수를 계산할 것이다. 점수는 자신의 수에서 자신의 왼쪽에 있는 수 중 선택된 수의 갯수를 뺀 값이다.

이렇게 고른 수 각각에 그 점수를 계산 한 후 전체 점수는 계산된 점수들의 합이다. 여러분은 전체 점수가 최대가 되도록 K 개의 수를 골라야 한다.

 

예를 들어서 N = 5 개의 자연수가 순서대로 2 3 1 2 1 로 주어지고, K = 3 이라고 하자. 만약 첫 번째 2 와 두 개의 1을 골랐다면, 각 수의 점수를 계산해서 나열하면 2 0 -1 과 같다. 따라서 전체 점수는 1 이다.

만약 첫 번째 2 와 3, 그리고 두 번째 2 를 고르고, 각 수의 점수를 계산해서 나열하면 2 2 0 과 같다. 따라서 전체 점수는 4 이다.

이 예시에서 전체 점수의 최대값은 4 이다.

 

N 개의 자연수 배열과 양의 정수 K 가 주어질 때, 전체 점수의 최대값을 출력하는 프로그램을 작성하시오.

 

* 입력

첫 번째 줄에 N 과 K 가 공백 하나를 사이로 두고 주어진다.

두 번째 줄에 N 개의 자연수가 공백 하나를 사이에 두고 주어진다.

 

* 출력

첫 번째 줄에 주어진 N 개의 수 중 K 개의 수를 고를 때, 전체 점수의 최대값을 출력한다.

 

* 제한

- 1 <= N <= 5,000

- 1 <= K <= N

- 주어지는 자연수는 1 이상 100,000 이하

 

* 예시

 

* 해결 과정

어떤 특정한 수를 주어진 갯수만큼 고르고 난 다음, 각 수 별로 현재 수의 왼쪽에 있는 숫자 중에서 자신과 같이 선택된 숫자의 갯수만큼을 빼는 방식으로 점수를 구한다.

이 점수를 최대화 하려면 주어진 숫자들 중에서 가장 큰 값을 우선적으로 주어진 갯수만큼 선택하되, 그 숫자들에서 뺄셈을 하게되는 숫자의 크기를 최소화 해야 한다.

그러려면 주어진 숫자들을 내림차순으로 정렬해준 다음, 가장 왼쪽에 있는 숫자부터 순서대로 선택해주면 가장 큰 숫자를 고르면서 각 숫자에 대해 뺄셈을 하게 되는 숫자의 크기 또한 최소화 시키는 것이 가능해진다.

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Collections;

public class Main {
    public static void main(String[] args) throws IOException {
        new Main().solution();
    }

    private void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] input = br.readLine().split(" ");
        int size = Integer.parseInt(input[0]);
        int count = Integer.parseInt(input[1]);

        Integer[] numberArray = new Integer[size];

        input = br.readLine().split(" ");
        for (int i = 0; i < input.length; i++) {
            numberArray[i] = Integer.parseInt(input[i]);
        }

        Arrays.sort(numberArray, Collections.reverseOrder());

        int result = 0;
        for (int i = 0; i < count; i++) {
            result += (numberArray[i] - i);
        }

        bw.write(result + "\n");
        bw.flush();
        bw.close();
    }
}

 

현재 상황에서 최적의 해답을 선택한다. -> 내림차순 정렬한 배열의 왼쪽에서 부터 매 반복마다 순서대로 따라오는 숫자들을 선택한다.

선택된 해답이 조건을 만족하는지 검사한다. -> 반복이 끝날 때 까지는 각 단계마다 합산해서 구한 점수가 최대값에 해당될 수 없으므로 위에서와 같이 계속 반복을 수행하면서 최적의 해답을 선택하여 전체 점수에 합산해준다.

 

위와 같은 과정을 거쳐 반복문을 끝낸 결과 최적해에 가까운 최대값을 구할 수 있었으므로 그리디 알고리즘 문제에 해당된다.