백준 21599 - 아이템 배치하기 (자바 - 그리디)

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

21599번: 아이템 배치하기

 

* 문제 요약

최근 싸이컴에서 제작한 게임 '입부 전쟁' 에서는 다양한 아이템을 활용해 전쟁의, 승리 확률을 높일 수 있습니다.

아이템은 한 번에 N개씩 강화할 수 있습니다.

강화력이 각각 A1, A2, ... AN 인 N 개의 아이템을 강화하려고 할 때, 아이템을 강화하는 방법은 다음과 같습니다.

- N개의 아이템을 적절한 순서로 원형으로 배열합니다.

- i번 아이템은 자신부터 시작해, 시계 방향으로 Ai 개의 아이템을 강화시킵니다. Ai = 0 인 아이템의 경우 다른 아이템에게 아무런 영향도 주지 않습니다.

- 만약 위 규칙에 의해 여러번 강화되는 아이템이 있다면, 실제로는 한 번만 강화됩니다.

 

브루는 '입부 전쟁' 세계 1위를 기록한 흑왕을 이기기 위해 아이템을 강화하려고 합니다. 하지만 브루는 어떤식으로 배치해야 최대한 많은 아이템을 강화할 수 있을지 찾지 못했고, 당신에게 도움을 요청했습니다.

그러나 당신도 '입부 전쟁' 게임을 열정적으로 하는 플레이어이기 때문에, 브루의 아이템 강화를 방해하려고 합니다.

따라서 당신은 브루의 부탁대로 가장 많은 아이템을 강화하게 하는 대신 가장 적은 아이템을 강화시키는 방법을 찾으려고 합니다.

 

N개의 아이템과 각각의 강화력 A1, A2, ... AN 이 주어졌을 때, 최대한 적은 아이템만 강화되게 하고, 그때 강화되는 아이템의 수를 구해 출력하세요.

 

* 입력

첫 줄에는 아이템의 수를 나타내는 정수 N 이 주어집니다.

둘째 줄에는 각 아이템의 강화력을 나타내는 정수 A1, A2, ... AN 이 주어집니다.

 

* 출력

가능한 모든 아이템 배치들 중에서, 강화되는 아이템 수의 최솟값을 출력합니다.

 

* 제한

- 1 <= N <= 5 * 10^5

- 0 <= Ai <= N

 

* 예시

 

* 해결 과정

숫자가 0 이 아닌 한 반복문을 탐색하며 숫자를 발견했을 시 그 아이템은 반드시 강화된다고 봐야 한다.

아이템을 최소로 강화해야 한답시고 강화력이 0 인 아이템만 강화해서 아무 아이템도 강화 안되게끔 하거나, 강화력이 1인 아이템만 강화하는 방식은 허용되지 않는다.

일단 강화력이 있는 아이템은 모두 강화해줘야 한다. 사실상 강화될 수 있는 아이템의 최솟값을 구하는게 아니라 최대값을 구해야 하는 문제인것 같다.

 

입력받은 숫자들 중에서 만약 최솟값이 1보다 크거나 같다면, 확정적으로 모든 아이템이 강화된다는 뜻이므로 입력받은 데이터의 갯수를 출력시켜 준다.

그렇지 않을 경우 아래의 로직을 수행한다.

1. 시작점에서 부터 강화가 어디까지 가능한지 보다 쉽게 측정하기 위해 입력받은 숫자들을 내림차순 정렬해주고 강화가 최대 어디까지 가는지 측정하기 위해 maxIndex 변수를 선언해준 후 0 으로 초기화 해준다.

2. 반복문을 수행하며 현재 탐색중인 데이터의 값이 0 인 경우 건너 뛰고 아닐 경우 배열의 시작점을 기준으로 현재 데이터가 시계 방향(오른쪽) 으로 강화 시킬수 있는 길이(index) 와 현재까지 강화된 최대 길이(maxIndex) 둘을 비교하여 더 큰값을 maxIndex 에 초기화 해준다.

3. 반복문이 끝나고 강화가 가능한 아이템의 최대 길이 + 1 (배열의 인덱스를 기준으로 길이를 구했으므로 + 1 을 해줘야 정확하게 강화가 가능한 아이템의 갯수를 알 수 있다.) 가 배열의 길이보다 긴 경우, 각 아이템을 강화 시킨 결과 그 영향력이 배열 전체의 길이를 초과. 즉, 한 바퀴 도는 것도 모자라 조금 더 길게 영향력이 미쳤다는 뜻인데 이는 모든 아이템이 강화 되었다는 뜻이다. 그렇기 때문에 배열의 길이를 정답으로 출력해준다.

4. 만약 배열의, 첫번째 값이 0 인 경우 내림차순 정렬을 했음에도 불구하고 첫번째 숫자가 0 이라는 것은 입력받은 모든 데이터들의 강화력이 0 이라는 뜻인데, 이는 모든 아이템을 강화할 수 없다는 말이므로 0 을 출력시켜준다.

5. 3,4 에 해당되지 않는 경우 maxIndex + 1 을 정답으로 출력시켜 준다.

 

* 코드

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 NumberFormatException, IOException {
        new Main().solution();
    }

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

        int size = Integer.parseInt(br.readLine());
        Integer[] array = new Integer[size];
        String[] input = br.readLine().split(" ");
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < size; i++) {
            array[i] = Integer.parseInt(input[i]);
            min = Math.min(min, array[i]);
        }

        Arrays.sort(array, Collections.reverseOrder());
        int maxIndex = 0;

        if (min >= 1) {
            bw.write(size + "\n");
        } else {
            for (int i = 0; i < array.length; i++) {
                if (array[i] == 0)
                    continue;
                else {
                    int index = i + array[i] - 1;
                    maxIndex = Math.max(index, maxIndex);
                }
            }
            if (maxIndex + 1 > array.length) {
                bw.write(array.length + "\n");
            } else if (array[0] == 0) {
                bw.write(0 + "\n");
            } else {
                bw.write((maxIndex + 1) + "\n");
            }
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

 

현재 상황에서 최적의 해답을 선택한다. -> 매 반복단계마다 현재 탐색중인 아이템의 강화력에 따라 배열의 시작점을 기준으로 어느정도 길이까지 강화가 되는지 확인하고, 기존의 최대 강화길이와 비교하여 더 큰값을 저장한다.

선택된 해답이 조건을 만족하는지 검사한다. -> 모든 데이터들을 탐색하기 전 까지는 최종 결과를 알 수 없으므로 반복문을 끝까지 지속한다.

 

위의 과정을 통해 문제를 해결하였으므로 그리디 알고리즘 문제에 해당된다.