반응형
https://www.acmicpc.net/problem/18111
18111번: 마인크래프트
팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게
www.acmicpc.net
구현 문제다.
가장 높은 높이부터 0까지 위에서 아래로 차례대로 계산해주는 함수를 호출하며 내려갔다.
로직은 간단한데 구현이 오래 걸린다.
채울 때는 시간을 1초 추가해주는 것도 있지만,
박스가 충분한지 확인해줘야 한다.
출력은 가장 높은 높이의 값을 출력해줘야 해서 우선순위 큐를 사용했다.
코드
import java.io.*;
import java.math.BigInteger; // subtract , multiply, add, mod
import java.util.*;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static StringTokenizer st;
static StringBuilder sb = new StringBuilder();
static int[][] arr;
static int[] temp;
static int globalMin = Integer.MAX_VALUE;
static int globalMax = Integer.MIN_VALUE;
static int[] su;
public static void main(String[] args) throws IOException {
// 입력부
StringTokenizer st = new StringTokenizer(br.readLine());
int low = Integer.parseInt(st.nextToken());
int col = Integer.parseInt(st.nextToken());
int boxes = Integer.parseInt(st.nextToken());
int maxHeight = 0;
arr = new int[low][col];
for(int i = 0 ; i<low; i++){
st = new StringTokenizer(br.readLine(), " ");
for(int j = 0; j<col; j++ ) {
int num = Integer.parseInt(st.nextToken());
arr[i][j] = num;
maxHeight = Math.max(maxHeight, num);
}
}
int ans = Integer.MAX_VALUE;
Queue<HB> q = new PriorityQueue<HB>((o1, o2)->{
if( o1.time == o2.time)
return o2.height - o1.height;
return o1.time - o2.time;
});
for(int i = maxHeight; i>=0; i--){
int[] answer = findTime(i, boxes, arr);
q.offer(new HB(answer[0], answer[1]));
}
System.out.println(q.poll());
}
public static int[] findTime(int height, int boxes, int[][] arr){
int[] ans = new int[2];
int time = 0;
// 제거시간
for(int i = 0 ; i<arr.length; i++){
for(int j = 0; j<arr[0].length; j++){
if(arr[i][j] > height){
int tt = arr[i][j] - height;
time += tt * 2; // 제거 2초
boxes += tt;
}
}
}
// 채우기 시간
for(int i = 0 ; i<arr.length; i++){
for(int j = 0; j<arr[0].length; j++){
if(arr[i][j] < height){
int tt = height - arr[i][j];
time += tt; // 설치 1초
boxes -= tt;
if(boxes < 0) {
ans[0] =Integer.MAX_VALUE;
return ans;
}
}
}
}
ans[0] = time;
ans[1] = height;
return ans;
}
}
class HB{
int time;
int height;
public HB(int time, int height){
this.time = time;
this.height = height;
}
public String toString(){
return this.time + " " + this.height;
}
}반응형
'문제풀이 > 코딩 문제 풀이' 카테고리의 다른 글
| [백준] 15686번 치킨배달 - JAVA (0) | 2022.06.11 |
|---|---|
| [백준] 1326번 폴짝폴짝 - JAVA (0) | 2022.06.09 |
| [백준] 1699번 제곱수의 합 - JAVA (0) | 2022.06.08 |
| [백준] 2206번 벽 부수고 이동하기 (0) | 2022.06.01 |
| [백준] 14501번 퇴사 (JAVA) (0) | 2022.04.21 |
