백준 20115 자바 - 에너지 드링크 (BOJ 20115 JAVA)

문제 : boj20115

 

 

  어떻게 해야 최대치가 될까? '/2'를 통해 줄어드는 양을 최소화 하면 된다. 그렇다면 일단 합친 값에 대해 추가로 '/2' 연산을 하면 안된다는 점을 알 수 있다. 예를들어 A, B, C가 있을 때 A에 B를 부어서 A가 A+B/2 가 됬다 해보자. 이 용액을 추가로 C에 부어버린다면 C = C + A/2 + B/4가 되는 셈이다. 즉 이미 합쳐진 용액은 더이상 건들지 않는것이 이득이다.

 

  그럼 N개의 용액 중 1개에다가 나머지를 전부 부어버리는 것이 이득임을 알 수 있고, 전체 수치가 최대가 되려면 가장 큰 값을 가지는 용액에다가 나머지 전부를 부어야 함을 알 수 있다. 따라서 단순히 매번 입력을 받으면서 그 중 max 값을 찾고, 모든 용액을 더한다(sum). 최종적으로 답은 max+(sum-max)/2 가 된다.

 

 

코드 : github

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

public class Main extends FastInput {
    private void solution() throws Exception {
        int n = nextInt();
        int max = 0;
        long sum = 0;
        while (n-->0){
            int cur = nextInt();
            if (cur>max) max = cur;
            sum+=cur;
        }
        System.out.println(max+(sum-max)/2d);
    }

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

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

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

    protected 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++];
    }
}