[Java] 백준(실버-2) 18111번 - 마인크래프트
문제 풀이
이번 문제는 완전 탐색을 이용해 풀 수 있는 문제이다.
아이디어 도출
이 문제는 완전탐색을 통해 주어진 2차원 배열을 순회하면서 조건에 부합하는지를 확인하면 된다.
문제 풀이를 위한 아이디어를 살펴보자.
- 땅을 평탄화하기 위해 쌓을 수 있는 최소 층과 최대 층 수를 구한다.
- 층별로 블록을 채우거나 제거한 후의 블록의 개수가 0개 이상(양수)이어야 한다.
- 층별로 평탄화 작업에 걸리는 시간을 통해 가장 적게 걸리는 최소시간과 그때의 층수를 구하면 된다.
말로만 들으면 잘 모를 수 있으니 예시를 들어보자.
1
2
3
2 2 2
5 1
2 5
위 입력예제를 들어보았을 때, 가장 낮은 블록의 높이는 1층부터 가장 높은 블록의 높이는 5층까지 존재한다. 이를 통해 우리가 평탄화를 통해 만들 수 있는 땅의 높이는 1층부터 5층까지 만들 수 있다는 것이다. 그러면 단순하게 1~5까지 순회하며 평탄화 작업을 실시하여 걸리는 시간을 계산하면 된다.
1층으로 만들 경우
1
2
3
4
5
6
7
5층 -> 1층으로 만들기 위해 블록을 제거한다. 얻는 블록의 수는 4개이며, 평탄화 작업에 걸리는 시간은 8초이다.
1층 -> 층이 같기에 작업 필요 X
2층 -> 1층으로 만들기 위해 블록을 제거한다. 얻는 블록의 수는 1개이며, 평탄화 작업에 걸리는 시간은 2초이다.
5층 -> 1층으로 만들기 위해 블록을 제거한다. 얻는 블록의 수는 4개이며, 평탄화 작업에 걸리는 시간은 8초이다.
총 평탄화 작업 시간: 18초
인벤토리 블록의 개수: 11개(기존2개+8개)
2층으로 만들 경우
1
2
3
4
5
6
7
5층 -> 2층으로 만들기 위해 블록을 제거한다. 얻는 블록의 수는 3개이며, 평탄화 작업에 걸리는 시간은 6초이다.
1층 -> 2층으로 만들기 위해 블록을 채운다. 차감되는 블록 수는 -1개이며, 평탄화 작업에 걸리는 시간은 1초이다.
2층 -> 층이 같기에 작업 필요 X
5층 -> 2층으로 만들기 위해 블록을 제거한다. 얻는 블록의 수는 3개이며, 평탄화 작업에 걸리는 시간은 6초이다.
총 평탄화 작업 시간: 13초
인벤토리 블록의 개수: 7개(기존2개+5개)
3층으로 만들 경우
1
2
3
4
5
6
7
5층 -> 3층으로 만들기 위해 블록을 제거한다. 얻는 블록의 수는 2개이며, 평탄화 작업에 걸리는 시간은 4초이다.
1층 -> 3층으로 만들기 위해 블록을 채운다. 차감되는 블록 수는 -2개이며, 평탄화 작업에 걸리는 시간은 2초이다.
2층 -> 3층으로 만들기 위해 블록을 채운다. 차감되는 블록 수는 -1개이며, 평탄화 작업에 걸리는 시간은 1초이다.
5층 -> 3층으로 만들기 위해 블록을 제거한다. 얻는 블록의 수는 2개이며, 평탄화 작업에 걸리는 시간은 4초이다.
총 평탄화 작업 시간: 11초
인벤토리 블록의 개수: 3개(기존2개+1개)
4층으로 만들 경우
1
2
3
4
5
6
7
5층 -> 4층으로 만들기 위해 블록을 제거한다. 얻는 블록의 수는 1개이며, 평탄화 작업에 걸리는 시간은 2초이다.
1층 -> 4층으로 만들기 위해 블록을 채운다. 차감되는 블록 수는 -3개이며, 평탄화 작업에 걸리는 시간은 3초이다.
2층 -> 4층으로 만들기 위해 블록을 채운다. 차감되는 블록 수는 -2개이며, 평탄화 작업에 걸리는 시간은 2초이다.
5층 -> 4층으로 만들기 위해 블록을 제거한다. 얻는 블록의 수는 1개이며, 평탄화 작업에 걸리는 시간은 2초이다.
총 평탄화 작업 시간: 9초
인벤토리 블록의 개수: -1개(기존2개+(-3개))
5층으로 만들 경우
1
2
3
4
5
6
7
5층 -> 층이 같기에 작업 필요 X
1층 -> 5층으로 만들기 위해 블록을 채운다. 차감되는 블록 수는 -4개이며, 평탄화 작업에 걸리는 시간은 4초이다.
2층 -> 5층으로 만들기 위해 블록을 채운다. 차감되는 블록 수는 -3개이며, 평탄화 작업에 걸리는 시간은 3초이다.
5층 -> 층이 같기에 작업 필요 X
총 평탄화 작업 시간: 7초
인벤토리 블록의 개수: -5개(기존2개+(-7개))
위와 같이 1층부터 5층까지 평탄화 작업을 실시해가면서 구해낸 최소시간은 11초이며, 11초가 걸리는 층수는 3층이 된다는 것을 볼 수 있다.
4층과 5층은 블록의 개수가 음수가 되어 블록을 채울 수 없기 때문에 조건에 부합하지 않는다.
문제 풀이를 위해 작성한 코드는 아래와 같다.
작성코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
package java_study;
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
int[][] arr = new int[N][M];
// 만들 수 있는 가장 낮은 층과 가장 높은 층
int min_height = Integer.MAX_VALUE;
int max_height = Integer.MIN_VALUE;
for(int i=0; i<N; i++) {
st = new StringTokenizer(br.readLine());
for(int j=0; j<M; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
min_height = Math.min(min_height, arr[i][j]);
max_height = Math.max(max_height, arr[i][j]);
}
}
// 가장 낮은 층부터 가장 높은 층까지 작업에 걸리는 시간 중 최소시간을 담을 time 변수
int time = Integer.MAX_VALUE;
// 최소시간일 경우 땅의 높이를 담을 floor 변수
int floor = 0;
/**
* 가장 낮은 층부터 높은 층까지 평탄화를 해가면서 층별로 걸리는 시간을 구한다.
* 이때, 가장 최소시간이 걸리는 시간과 층수를 구하면 된다.
*/
for(int idx=min_height; idx<=max_height; idx++) {
// 층별로 작업에 걸리는 시간을 담을 sec 변수
int sec = 0;
// 층별로 작업 이후 인벤토리에 남은 블록의 개수
int block = B;
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
/*
* 현재 블록의 높이가 만들어야 할 층보다 높다면 블록을 깎아 인벤토리에 넣는다.
* 블록을 깎을 때는 2배만큼 시간이 걸린다.
*/
if(arr[i][j] > idx) {
sec += (arr[i][j] - idx) * 2;
block += (arr[i][j] - idx);
}
/**
* 현재 블록의 높이가 만드렁야 할 층보다 낮다면 인벤토리에 있는 블록으로 채운다.
* 블록을 채울 때는 1배만큼 시간이 걸린다.
*/
else if(arr[i][j] < idx) {
sec += (idx - arr[i][j]);
block -= (idx - arr[i][j]);
}
}
}
// 블록의 개수가 음수라면 블록을 채울 수가 없기 때문에 조건에 맞지 않는다.
if(block < 0) {
break;
}
// 층별로 작업에 걸린 시간이 이전 층의 작업 시간보다 적다면, 현재 층의 작업시간과 층수를 저장한다.
if(time >= sec) {
time = sec;
floor = idx;
}
}
bw.write(time + " " + floor + "\n");
bw.close();
br.close();
}
}
출처
- 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.