문제
팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 땅을 파거나 집을 지을 수 있는 게임이다.
목재를 충분히 모은 lvalue는 집을 짓기로 하였다. 하지만 고르지 않은 땅에는 집을 지을 수 없기 때문에 땅의 높이를 모두 동일하게 만드는 ‘땅 고르기’ 작업을 해야 한다.
lvalue는 세로 N, 가로 M 크기의 집터를 골랐다. 집터 맨 왼쪽 위의 좌표는 (0, 0)이다. 우리의 목적은 이 집터 내의 땅의 높이를 일정하게 바꾸는 것이다. 우리는 다음과 같은 두 종류의 작업을 할 수 있다.
- 좌표 (i, j)의 가장 위에 있는 블록을 제거하여 인벤토리에 넣는다.
- 인벤토리에서 블록 하나를 꺼내어 좌표 (i, j)의 가장 위에 있는 블록 위에 놓는다.
1번 작업은 2초가 걸리며, 2번 작업은 1초가 걸린다. 밤에는 무서운 몬스터들이 나오기 때문에 최대한 빨리 땅 고르기 작업을 마쳐야 한다. ‘땅 고르기’ 작업에 걸리는 최소 시간과 그 경우 땅의 높이를 출력하시오.
단, 집터 아래에 동굴 등 빈 공간은 존재하지 않으며, 집터 바깥에서 블록을 가져올 수 없다. 또한, 작업을 시작할 때 인벤토리에는 B개의 블록이 들어 있다. 땅의 높이는 256블록을 초과할 수 없으며, 음수가 될 수 없다.
입력
첫째 줄에 N, M, B가 주어진다. (1 ≤ M, N ≤ 500, 0 ≤ B ≤ 6.4 × 107)
둘째 줄부터 N개의 줄에 각각 M개의 정수로 땅의 높이가 주어진다. (i + 2) 번째 줄의 (j + 1) 번째 수는 좌표 (i, j)에서의 땅의 높이를 나타낸다. 땅의 높이는 256보다 작거나 같은 자연수 또는 0이다.
출력
첫째 줄에 땅을 고르는 데 걸리는 시간과 땅의 높이를 출력하시오. 답이 여러 개 있다면 그중에서 땅의 높이가 가장 높은 것을 출력하시오.
문제 접근 방법
땅의 높이를 평평하게 맞추기 위해서는
1. 블록을 제거하거나
2. 블록을 새로 놓거나
두 가지의 방법을 선택할 수 있다. 이때, 제거하는 방법은 2초, 새로 놓는 방법은 1초가 걸린다. 두 방법을 선택하려면 기준이 되려는 층이 필요한데 이 기준층은 문제에서 주어진 높이의 최저층과 최고층 사이에 있을 것이다. 그렇다면 기준층을 어떻게 정하느냐가 문제가 된다.
이때, 고려해야 할 점은 인벤토리에 있는 블록의 개수는 B개로 정해져 있다.
= 이 말은 즉, 블록을 새로 놓는 개수에는 제한이 있다는 소리이다.
= 블록을 놓는다는 것은 높은 층에 맞춰 낮은 층에 블록을 더 놓는다는 말이 되고
= 기준층을 높게 잡는다는 뜻이다.
그렇다면 인벤토리에 있는 B개를 다 써버리면 기준층에 맞게 블록을 다 채워놓지 못하는 상황이 벌어질 수도 있다.
그렇다면 제일 낮은 층에 맞춰 기준층을 잡아보고, 점점 한층씩 기준층을 올려가면서 땅을 평평하게 맞추는 데 걸리는 시간을 계산해준다.
이때, 언제까지 기준층을 올려야 하나?라는 의문이 생길 것이다. 그러나 우리는 알고 있다. 문제에서 블록을 제거하는 방법이 새로 놓는 방법보다 시간이 1초 더 걸린다고 주어줬다. 따라서 인벤토리에 있는 블록이 부족하지 않은 선에서 기준층을 최대한 높이는 것이 시간이 최소한으로 걸릴 가능성이 높아진다.
따라서 반복문을 설정할 때 반복문을 멈춰 줄 조건으로는
1. 기준층이 초기 상태 최대층 이하일 때까지만 반복
2. 기준층에 맞춰 블록을 추가하면 인벤토리에 있는 블록이 부족하면 종료
두 가지를 설정하여 반복을 중단해줘야 한다.
층을 최대한 높여도 시간이 최소가 아닐 수도 있다. 따라서 시간이 줄어든 경우에 한해서만 변수를 변경할 수 있도록 해주어야 하고, 답이 여러 개 일시 땅 높이가 최대인 것을 답으로 내라고 했으므로 이점도 고려해주어야 한다.
JAVA 코드 풀이
import java.util.*;
import java.io.*;
public class Main {
public static void main(String args[]) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer init = new StringTokenizer(br.readLine());
int n = Integer.parseInt(init.nextToken()); // ROW size
int m = Integer.parseInt(init.nextToken()); // COL size
int b = Integer.parseInt(init.nextToken()); // 인벤토리 저장된 블럭 수
int ground[][] = new int[n][m];
int high = 0, low = Integer.MAX_VALUE;
for(int i=0; i<n; i++){
StringTokenizer col = new StringTokenizer(br.readLine());
for(int j=0; j<m; j++){
ground[i][j] = Integer.parseInt(col.nextToken());
high = Math.max(high, ground[i][j]);
low = Math.min(low, ground[i][j]);
}
}
int time;
int ans = Integer.MAX_VALUE; // 걸린 시간
int ansLevel = -1; // 기준층
int temp = low; // 기준층 가정
int cnt; // 추가로 사용된 블럭 수
while(temp <= high){ // 기준층이 초기상태 최고층 이하일때 까지만 반복
time = 0;
cnt = 0;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(ground[i][j] > temp) { // 기준층보다 블럭이 많은 경우 = 블럭 제거
time += (ground[i][j] - temp)*2;
cnt -= ground[i][j] - temp;
}
else if(ground[i][j] < temp) { // 기준층보다 블럭이 적은 경우 = 블럭 추가
time += temp - ground[i][j];
cnt += temp - ground[i][j];
}
}
}
if(cnt > b) // 인벤토리의 블럭보다 더 많은양 사용
break;
if(ans > time){ // 이전 기준층보다 시간 단축
ans = time;
ansLevel = temp;
}
else if(ans == time) // 이전 기준층과 시간이 같아 더 기준층이 더 높은 것을 답으로 채택
ansLevel = Math.max(temp, ansLevel);
temp++; // 기준층+1 다시 가정
}
System.out.println(ans+" "+ansLevel);
}
}
코드 실행 결과
후기
이번 문제는 문제가 어렵지는 않았으나, 코드 구동 원리를 고민하는데 시간이 조금 걸렸던 문제였다. 분명 더 깔끔하게, 더 효율적으로 코드를 작성할 수 있을 것 같은데 도저히 어떤 게 틀린 건지 문제가 틀려버린다. 좀 더 고민해보고 나중에 더 나은 코드가 생각나면 추가로 포스팅해보도록 하겠다.
문제 원본
'문제 풀이 > [JAVA_자바] 백준' 카테고리의 다른 글
[JAVA / 자바] 백준 10989번 - 수 정렬하기 3 (0) | 2022.01.27 |
---|---|
[JAVA / 자바] 백준 2805번 - 나무 자르기 (0) | 2022.01.26 |
[JAVA / 자바] 백준 2108번 - 통계학 (0) | 2022.01.24 |
[JAVA / 자바] 백준 2751번 - 수 정렬하기 2 (0) | 2022.01.21 |
[JAVA / 자바] 백준 1920번 - 수 찾기 (0) | 2022.01.20 |