백준 10373 자바 - Buffcraft (BOJ 10373 JAVA)

문제 : boj10373

 

 

1. 문제 정의

  상당히 문제가 불친절하다. 예제라도 의미 있을 예제를 들어주면 좋을텐데 ㅡㅡ; 상당히 별로인 문제이다.

 

1.1 'The following line must contain n different numbers', 'The last line of the output must contain m different numbers' 에 따라 출력을 해줘야 하는데, 그럼 following line이 0이라 출력할 게 없으면 줄을 띄워야 되나 말아야 하나라는 문제점이 있다(second, third line이라고 하던지.. 저렇게 하면 사실 following line이 last line이 되기도 하므로 애매하다.). 원래 문제대로라면 줄을 띄워야 맞지만(해당 대회 문제 채점 데이터 확인함), 백준 채점시스템이 둘 다 통과시켜주니 상관은 없다.

 

1.2 출력쪽에 보면 '0 ≤ n + m ≤ k' 라는게 있어서 애초에 입력값 중 Cd와 Cp의 합도 k보다 작을 것 같이 착각할 수 있는데, 확인해보니 아니다. Cd + Cp는 k보다 커질 수 있다. 물론 Cd+Cp보다 k가 클수도 있다. 그러니 이 부분에 대한 예외처리를 잘 해야 한다.

 

1.3 문제 설명을 보면 'only the last k buffs remains active' 라고 되있는데, 입력 순서와는 전혀 상관이 없다. 왜 저따구로 적어놨는지 잘 모르겠다. 그냥 입력순서 상관없이 선택한 k개의 버프만 유효하다고 보면 된다. 또한 그 k는 Direct 버프와 Percentage 버프를 합친 값이다.

 

  결론적으로 이 문제는 입력 순서와 관계없이 n개의 Direct 버프를 임의로 선택한 개수와 m개의 Percentage 버프를 임의로 선택한 개수의 합이 k개 이하면서(n+m<=k) 최고 버프 수치인 경우를 찾는 문제이다.

 

 

2. 풀이 방법

  모든 버프는 0이상이므로 결국 n+m = min(n+m, k)이 되도록 Direct 버프에서 제일 좋은 버프 n개를 고르고, Percentage 버프에서 제일 좋은 버프 m개를 고르기만 하면 된다. 이 때 n과 m을 몇으로 선택할지가 관건인데, k가 50000이하의 값이므로 모든 경우(n=0, m=50000 / 1, 49999 / ... / 50000, 0)를 봐도 5만번이면 된다.

  

  그럼 필요한건 다음과 같다.

A. Direct 버프 중 임의의 n개의 최대 합을 알 수 있어야한다. -> 내림차순 정렬 후 누적합을 구하자.

 

B. Percentage 버프 중 임의의 m개의 최대 합을 알 수 있어야 한다. -> 마찬가지로 내림차순 정렬 후 누적합! 

 

C. 'A', 'B'가 해결된다면 그 이후로는 단순히 n=0부터 n=min(Cd, k)까지 보면서, m=min(Cp, k-n)으로 m개를 선택하면 된다.

 

그럼 시간복잡도는 O(NlogN[정렬] + N[누적합 계산] + N[최대 합 찾기]) = O(NlogN) 가 된다.

 

 

 

코드 : github

import java.io.DataInputStream;
import java.io.IOException;
import java.util.Arrays;

class Buff implements Comparable<Buff> {
    int idx, value;
    public Buff(int idx, int value) {
        this.idx = idx;
        this.value = value;
    }
    public void add(Buff b) {
        this.value += b.value;
    }

    @Override
    public int compareTo(Buff o) {
        return o.value - this.value;
    }
}

public class Main {
    private static long getBuffSum(int b, int dSum, int pSum) {
        return 1l*(b+dSum)*(100+pSum);
    }

    private static void solution() throws Exception {
        int b = nextInt();
        int k = nextInt();
        int n1 = nextInt();
        int n2 = nextInt();

        if (n1+n2 <= k) {
            StringBuilder sb = new StringBuilder();
            sb.append(n1).append(' ').append(n2).append('\n');
            if (n1 != 0) {
                for (int i = 1; i <= n1; i++) sb.append(i).append(' ');
                sb.append('\n');
            }
            
            for (int i = 1; i <= n2; i++) sb.append(i).append(' ');
            System.out.print(sb);
            return;
        }

        Buff[] arr1 = new Buff[n1];
        Buff[] arr2 = new Buff[n2];
        for (int i = 0; i < n1; i++) arr1[i] = new Buff(i, nextInt());
        for (int i = 0; i < n2; i++) arr2[i] = new Buff(i, nextInt());

        //sort
        Arrays.sort(arr1);
        Arrays.sort(arr2);

        //prefix sum
        for (int i = 1; i < arr1.length; i++) arr1[i].add(arr1[i-1]);
        for (int i = 1; i < arr2.length; i++) arr2[i].add(arr2[i-1]);

        //solve
        int maxDi = 0;
        int maxPi = 0;
        long max = 0l;
        int loopLen = Math.min(k, n1);
        for (int di = 0; di <= loopLen; di++) {
            int pi = Math.min(k-di, n2);
            long sum = getBuffSum(b, di==0?0:arr1[di-1].value, pi==0?0:arr2[pi-1].value);
            if (max < sum) {
                max = sum;
                maxDi = di;
                maxPi = pi;
            }
        }

        StringBuilder sb = new StringBuilder();
        sb.append(maxDi).append(' ').append(maxPi).append('\n');
        if (maxDi != 0) {
            for (int i = 0; i < maxDi; i++) {
                sb.append(arr1[i].idx + 1).append(' ');
            }
            sb.append('\n');
        }
        
        for (int i = 0; i < maxPi; i++) {
            sb.append(arr2[i].idx+1).append(' ');
        }
        System.out.print(sb);
    }

    public static void main(String[] args) throws Exception {
        initFI();
        solution();
    }

    private static final int DEFAULT_BUFFER_SIZE = 1 << 16;
    private static DataInputStream inputStream;
    private static byte[] buffer;
    private static int curIdx, maxIdx;

    private static void initFI() {
        inputStream = new DataInputStream(System.in);
        buffer = new byte[DEFAULT_BUFFER_SIZE];
        curIdx = maxIdx = 0;
    }

    private static int nextInt() throws IOException {
        int ret = 0;
        byte c = read();
        while (c <= ' ') c = read();
        do {
            ret = ret * 10 + c - '0';
        } while ((c = read()) >= '0' && c <= '9');
        return ret;
    }

    private static byte read() throws IOException {
        if (curIdx == maxIdx) {
            maxIdx = inputStream.read(buffer, curIdx = 0, DEFAULT_BUFFER_SIZE);
            if (maxIdx == -1) buffer[0] = -1;
        }
        return buffer[curIdx++];
    }
}