Algorithm/Baekjoon
[Algorithm] Baekjoon 18111번 : 마인크래프트
MaxLevel
2023. 10. 10. 02:25
https://www.acmicpc.net/problem/18111
18111번: 마인크래프트
팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게
www.acmicpc.net
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
|
int n, m, b;
int arr[500][500] = { 0 };
int main(void)
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m >> b;
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
cin >> arr[i][j];
}
}
int answerTime = 0x3f3f3f3f;
int answerHeight = 0;
for (int height = 0; height <= 256; ++height)
{
if (height == 256)
{
int asdf = 0;
}
int blockCount = b; // 가지고 있는 블럭개수
int buildingCount = 0; // 블럭을 쌓아올린 횟수.
int removeCount = 0; // 블럭을 제거한 횟수.
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
if (arr[i][j] > height) // 블럭 제거해야하면
{
blockCount += arr[i][j] - height;
removeCount += arr[i][j] - height;
}
else if(arr[i][j] < height) // 블럭을 쌓아야하면
{
blockCount -= height - arr[i][j];
buildingCount += height - arr[i][j];
}
}
}
if (blockCount < 0) continue;
else
{
int time = removeCount * 2 + buildingCount;
if (time <= answerTime)
{
answerTime = time;
answerHeight = max(answerHeight, height);
}
}
}
cout << answerTime << ' ' << answerHeight;
}
|
cs |
파라매트릭 서치의 느낌을 가지고있는 완전탐색문제이다.
완전탐색을 돌려해도 무언가 '기준'이 있어야 시간이 오래걸리더라도 탐색을 하던가 말던가 할 수 있다.
그것에 대한 기준을 '높이'로 잡아버려서 해결한다.
즉 해당 높이로 평평하게 만들수있는지 없는지에 대한 검사 후, 만들 수 있으면 정답을 업데이트하면 된다.