[Java] 백준 18111번 마인크래프트

블럭의 층을 모두 같게 만들어주는 문제입니다.
가지고 있는 블럭이 주어지고 최소한의 개수로 동일한 층으로 만들고
방법이 여러개라면 최대한 높은층을 만들어줍니다.

1 2 1
3 4 2
3 3 1
위와 같이 9개의 블럭이 있을때 전부 3, 4, 5층으로 만들때 다음과 같이 만들 수있습니다.
(높은 층에서 낮은층을 만드는 경우는 잠시 예외 처리해두고 생각하겠습니다)

3층
1 = 3개*2
2 = 2개*1
3 = 3개*0
4 = 1개*0 
= 8개

4층
1 = 3개*3
2 = 2개*2
3 = 3개*1
4 = 1개*0
= 16개

5층
1 = 3개*4
2 = 2개*3
3 = 3개*2
4 = 1개*1
= 27개

여기서 규칙을 찾아보면 다음과 같습니다.
3층 8개
4층 3층개수 + (3 + 2 + 3)
5층 4층개수 + (3 + 2 + 3 + 1)

이전 층의 개수 + 각층의 블럭 개수 입니다.
이를 활용해서 N층을 만들때 몇개의 블럭을 쌓아야 하는지 알 수 있습니다.

반대로 N층을 만들기 위해 몇개의 블럭을 빼야하는지 구하기 위해서
256층 빼야하는 개수를 위와 같이 구해줍니다.

이제 각 층마다 추가해야하는 블럭 수, 빼야하는 블럭 수를 구했습니다.
각 층 마다 (배낭 + 추가해야하는 블럭 수 + 빼야하는 블럭 수)가 (0보다 큰 경우)를 해당 층을 만들 수 있는 경우로 판단합니다

판단된 층에서 (추가해야하는 블럭 수 * 1) + (빼야하는 블럭 수 * 2)로 시간을 구해줍니다.
가장 시간이 적으면서 높은층인 결과값을 출력해줍니다.

import java.io.*;
import java.util.*;

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 m = Integer.parseInt(st.nextToken());
		int bag = Integer.parseInt(st.nextToken());
		int ansTime = Integer.MAX_VALUE;
		int ansHeight = Integer.MIN_VALUE;
		int num;
		int numAsc = 0;
		int numDes = 0;
		int time = 0;
		int[] numArr = new int[257];
		int[] cumSumAsc = new int[257];
		int[] cumSumDes = new int[257];
		
		for(int i=0; i<n; ++i) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<m; ++j) {
				num = Integer.parseInt(st.nextToken());
				++numArr[num]; 
			}
		}
		
		for(int i=1; i<=256; ++i) {
			numAsc += numArr[i-1];
			cumSumAsc[i] += cumSumAsc[i-1] + numAsc;
		}
		for(int i=256-1; i>=0;--i) {
			numDes += numArr[i+1];
			cumSumDes[i] += cumSumDes[i+1] + numDes;
		}
		
		
		for(int i=0; i<=256; ++i) {
			if(bag + cumSumDes[i] - cumSumAsc[i] < 0 ) {
				continue;
			}
			time = cumSumAsc[i] + (cumSumDes[i] * 2);
			if(ansTime > time) {
				ansTime = time;
				ansHeight = i;
			} else if(ansTime == time) {
				ansHeight = Math.max(ansHeight, i);
			}
		}
		
		System.out.println(ansTime + " " + ansHeight);
	}
}