[코딩테스트] 백준 16112번: 5차 전직 - JAVA

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

Problem 💻

문제

메이플스토리 뉴비 키파가 드디어 레벨 200을 달성하고 5차 전직이라는 시스템을 이용해 캐릭터를 더욱 강력하게 만들려고 합니다. 5차 전직을 하려면 먼저 퀘스트를 통해 아케인스톤이라는 아이템을 받아야 합니다. 아케인스톤을 활성화시키면 캐릭터가 얻는 경험치를 아케인스톤에 모을 수 있습니다. 5차 전직을 하기 위해서는 총 n개의 퀘스트를 진행해서 n개의 아케인스톤을 받아야 하며, 각각의 아케인스톤에 5억 이상의 경험치를 모으면 5차 전직을 진행할 수 있는 자격이 주어집니다.

 

i번째 퀘스트를 진행하면 ai의 경험치와 i번째 아케인스톤이 주어집니다. 퀘스트로 얻는 경험치도 사냥으로 얻는 것과 똑같은 경험치이기 때문에, i번째 퀘스트의 보상 경험치를 받을 때 활성화되어 있던 아케인스톤에는 ai의 경험치가 추가됩니다.

 

원래 메이플스토리에서는 한 번에 하나의 아케인스톤만 활성화시켜 놓을 수 있고, 각각의 아케인스톤에는 최대 5억의 경험치를 채울 수 있습니다. 그러나 해킹에는 자신이 있었던 메린이 키파는 서버를 해킹해 아케인스톤의 최대 경험치 제한을 없애 버리고, 최대 k개의 아케인스톤이 동시에 활성화되어 있을 수 있도록 바꿨습니다. 따라서 한 퀘스트의 보상 경험치가 여러 개의 아케인스톤에 추가될 수 있습니다. 예를 들어 1번째와 3번째 아케인스톤이 활성화되어 있는 상태에서 2번째 퀘스트를 진행해 100,000의 경험치와 2번째 아케인스톤을 획득하면, 1번째와 3번째 아케인스톤에 각각 100,000의 경험치가 추가되고 2번째 아케인스톤은 모인 경험치가 0인 상태로 받게 됩니다.

 

키파는 퀘스트를 원하는 순서대로 진행할 수 있지만, 같은 퀘스트를 두 번 이상 진행할 수는 없습니다. 키파는 퀘스트를 진행하면서 아케인스톤을 적절히 활성화 또는 비활성화시켜서 아케인스톤에 모인 경험치의 합을 최대화하고 싶습니다. 모인 경험치의 합이 커지면 어쨌든 기분이 좋으니까요. 키파를 대신해서 이 값을 구해 주세요!

 

입력

첫째 줄에 정수 n과 k(1 ≤ k ≤ n ≤ 3 · 105)가 주어집니다.

둘째 줄에 n개의 정수가 공백을 사이에 두고 주어집니다. i번째 정수는 ai이며 0보다 크고 108보다 작거나 같습니다.

 

출력

첫째 줄에 키파가 아케인스톤에 모을 수 있는 경험치의 합의 최댓값을 출력합니다.

 

 

Solution 💡

문제를 이해하는 것이 가장 중요하다.

문제에서 퀘스트 n개가 주어지며 최대 활성화할 수 있는 아케인스톤의 값을 k로 명시한다.

 

퀘스트로 얻은 경험치는 활성화된 아케이스톤 모두에게 추가된다. 여기서 가장 최고효율을 낼 수 있는 방법을 찾아 총 모은 경험치의 합산을 출력하면 된다.

 

문제에서 주어진 가장 효율적인 방법은 경험치의 합산이 가장 큰 경우를 말한다. 잘 생각해보면 가장 작은 경험치를 가진 퀘스트를 깨서 얻어 아케인스톤을 활성화하고 그 아케인스톤에 상대적으로 큰 값을 지속적으로 추가해주면 가장 큰 값이 된다. 아무래도 큰 값을 활성화시키고 작은 값을 합산하면 효율이 떨어지게 된다.

 

그러기때문에 퀘스트를 오름차순으로 정렬하여 진행해야한다.

 

정렬한 퀘스트 루프를 실행하며 최대활성만큼 스톤을 증가시켜준다. 여기서 주의할 점은 퀘스트깨고 경험치를 분배한 후 스톤이 증가한다는 점이다. 스톤이 최대만큼 증가했다면 활성스톤만큼 분배를 해주면 된다.

(문제만 보고 비활성된 스톤에 한해서 활성된 스톤에 치환되는지 알았는데 예시를 보니 모든 퀘스트가 동일하게 치환된다는 것을 알 수 있다.)

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        // 높은 수를 나중에 진행해야 많은 스톤을 활성화 시켜 높은 점수를 얻을수 있다
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        // 퀘스트 수
        int N = Integer.parseInt(st.nextToken());
        // 활성화 시킬수 있는 스톤의 수
        int K = Integer.parseInt(st.nextToken());

        long[] arr = new long[N];

        StringTokenizer st1 = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st1.nextToken());
        }

        //오름차순
        Arrays.sort(arr);

        long max = 0;
        int getStone = 1;

        // 경험치는 활성화된 돌에 대해 + 되는 개념
        // 단, 주의할 점은 깬 다음에 활성 여부를 결정할 수 있는 것
        // 그래서 활성++가 뒤에 있는 것
        for (int i = 1; i < N; i++) {
            if (getStone < K) {
                max += arr[i] * getStone;
                getStone++;
            } else {
                max += arr[i] * getStone;
            }
        }

        System.out.println(max);
    }
}