[백준(BOJ)] 18111번 마인크래프트 C++

문제 : https://www.acmicpc.net/problem/18111

18111번: 마인크래프트

 

 

어떤 문제인가?

시작 전, 이 문제를 보니 어렸을 때 마인크래프트를 하던 기억이 떠올라 기분이 좋았다.

 

모든 입력들(땅의 높이)의 값이 같게 만들어야 하고 이때 걸리는 시간과 가장 큰 높이를 출력하면 된다.

 

 

접근 방법

 

int block[500][500];

먼저 땅이 높이를 저장할 2차원 배열을 선언해줬다.

 

int n, m, b;

cin >> n >> m >> b;

for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        cin >> block[i][j];
    }
}

문제의 요구대로 변수들을 선언하고 입력받았다.

그리고 2중 for문을 통해 2차원 배열의 인덱스 값을 입력받았다.

 

int finalTime = INT_MAX;
int finalH = 0;

 최종 시간과 최종 높이를 저장할 변수이다.

 

최종 시간 같은 경우는 경우의 수가 여러 가지일 때 최솟값이 되어야 한다.

최악의 경우 걸리는 시간을 계산하기 싫어서 그냥 INT_MAX로 초가 화해 주었다.

반대로 최종 높이는 최댓값이 되어야 하기 때문에 0으로 초기화해주었다.

 

 

 

이제 완전 탐색을 시작할 것이다.

땅의 높이가 0~256까지이니 땅의 높이를  i로 만드는 것이 가능한가, 가능하다면 걸리는 시간, 높이를 알아볼 것이다.

 

for (int h = 0; h <= 256; h++) {
    int blockToPlace = 0;
    int blockToRemove = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (h > block[i][j]) {
                blockToPlace += h - block[i][j];
            } else {
                blockToRemove += abs(h - block[i][j]);
            }
        }
    }

    if (b + blockToRemove >= blockToPlace) {

        int time = blockToPlace + blockToRemove * 2;

        if (time < finalTime) {
            finalTime = time;
            finalH = h;
        }

        if (time == finalTime) {
            if (h > finalH) {
                finalH = h;
            }
        }
    }
}

for문을 돌며 현재 만들려고 하는 높이(h)와 입력받은 높이들을 비교한다.

 

만약 h가 입력받은 높이보다 크면, 블록을 더 쌓아야 한다. -> blockToPlace를 h와 입력받은 높이의 차만큼 증가.

 

반대의 경우 블록을 제거해야 한다. -> blockToRemove를 h와 입력받은 높이의 차의 절댓값만큼 증가.

 

이제 쌓아야 할 블록과 제거해야 할 블록의 개수를 알았으니

현재 인벤토리에 갖고 있는 블록과 제거해서 생기는 블록 의의 개수를 통해 쌓아야 할 블록을 쌓을 수 있는지 확인해야 한다.

 

if (b + blockToRemove >= blockToPlace)

이 부분을 통해 가능 여부를 확인한다, 만약 가능하다면 소요시간을 계산한다.

블록을 쌓는 건 1초, 블록을 제거하는 건 2초.

만약 현재 걸린 시간이 최종 시간보다 작다면 현재 걸린 시간을 최종 시간으로 바꿔준다. 또 최종 높이를 현재 높이로 바꿔준다.

 

예외처리!

만약 현재 걸린 시간이 최종 시간과 같다면 둘 중 더 큰 높이를 최종 높이로 저장한다.

 

모든 경우의 수를 다 살펴보고 나면 최종 시간과 최종 높이가 결정됐을 것이다.

cout << finalTime << " " << finalH;

이를 출력해주면 끝!

 

 

 

무엇이 어려웠는가?

 

모든 경우의 수를 살펴봐야 하는 완전 탐색이라는 것을 알았지만 어떻게 모든 경우의 수를 살펴볼지를 고민했다.

 

처음엔 기준이 되는 한 높이를 정하고 그 기준이 되는 높이를 만들기 위해 나머지 높이에 블록을 쌓거나 제거하려는 방법을 생각했다.

 

근데 이 방법은 기준 높이를 정하는 것도 어떻게 할지 모르겠고, 결론은 이 방법은 틀린 것이라 생각했다.

 

완전 탐색이라는 것에 집중해 가능한 모든 범위의 높이들을 만들기 위해 필요한 시간을 비교하는 방법을 떠올렸다.

 

 

배운 점

 

완전 탐색이라는 것을 배우고 문제를 풀어서 그런지, 완전 탐색을 사용해야 한다고 생각이 나서 다행이다.

또, 완전탐색을 써야 한다는 것을 알아도, 어떤 것을 어떻게 탐색해야 할지 찾아내는 실력을 더 기르고 싶다.