백준 18111 (마인크래프트) c++

문제

18111번: 마인크래프트

다음과 같은 땅을 평평하게 만드는데 걸리는 최소 시간과 높이를 구하는 문제입니다.

땅을 평평하게 만드는 방법은 2가지가 있습니다.

1.  땅을 파기(시간이 2초가 걸립니다. 대신에 주어진 block이 1개 늘어납니다.)

2.  땅을 채우기(시간이 1초 걸립니다. 대신에 주어진 block이 1개 줄어듭니다. 주어진 block이 모자라면

땅을 채울 수 없습니다.)

 

처음에 이 문제를 접했을 때는 어떻게 진행해야 될지 감을 잡지 못해 구글에 찾아보았습니다.

문제의 접근 방식인 bruteforce 방법이란 것을 알고 스스로 다시 문제를 접근해 보았습니다.

 

풀이는 간단합니다. 땅의 높이를 0부터 256까지 반복하면서 최소 시간과 땅의 높이를 갱신해주면됩니다.

int min_time = MAX;
int inventory;
int height = 0;
bool check = false;
for (int i = 0; i <= 256; i++) {
    inventory = b;
    time = 0;
    for (int j = 0; j < n; j++) {
        for (int k = 0; k < m; k++) {
            if (arr[j][k] > i) {
                time += (arr[j][k] - i) * 2;
                inventory += arr[j][k] - i;
            }
            else if (arr[j][k] < i) {
                time += i - arr[j][k];
                inventory -= i - arr[j][k];                }
            }
        }
    if (inventory < 0)
        continue;
    if (time == min_time)
        height = i;
    else if (time < min_time) {
        min_time = min(min_time, time);
        height = i;
    }            
}
cout << min_time << ' ' << height;

변수 min_time에 다가 최소 시간을 넣어줄 것입니다.

변수 time은 임의의 변수입니다. 각 땅의 높이를 돌면서 시간을 계산해 min_time과 비교해 값을 갱신시켜줍니다.

변수 inventory는 현재 내가 갖고 있는 block의 개수를 의미합니다.

변수 height는 block의 높이입니다.

 

3중 for문을 진행하면서 i는 땅의 높이를 의미합니다.

임의의 땅의 높이에서 time과 inventory가 계산이 되었다면 

만약 inventory가 음수이면 위의 땅의 높이는 현재 만들 수 없으므로 continue를 하게 됩니다.

만약 최소시간이 같은 것이 여러개일 경우 더 높은 땅의 높이를 구해야 하므로 time = min_time일 때

height를 갱신해 주었습니다.

---

전체 코드입니다.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>
#include <tuple>
#define MAX 2100000000
#define inf LONG_MAX
using namespace std;
using ll = long long;
using ull = unsigned long long;
int arr[501][501];
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    int n, m, b;
    cin >> n >> m >> b;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> arr[i][j];
 
    int min_time = MAX;
    int time;
    int inventory;
    int height = 0;
    bool check = false;
    for (int i = 0; i <= 256; i++) {
        inventory = b;
        time = 0;
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < m; k++) {
                if (arr[j][k] > i) {
                    time += (arr[j][k] - i) * 2;
                    inventory += arr[j][k] - i;
                }
                else if (arr[j][k] < i) {
                    time += i - arr[j][k];
                    inventory -= i - arr[j][k];
                }
            }
        }
        if (inventory < 0)
            continue;
        if (time == min_time)
            height = i;
        else if (time < min_time) {
            min_time = min(min_time, time);
            height = i;
        }
    }
 
    cout << min_time << ' ' << height;
    
    return 0;
}