백준 18111 마인크래프트 c++ [컴공과고씨]

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

18111번: 마인크래프트

문제를 정리하면 땅 높이를 맞추어 주는 것인데 이제 땅을 쌓는건 1초, 깎는건 2초 걸리고 쌓을 때는 블록이 있어야 쌓을 수 있다.

최대높이가 256이기 때문에 땅을 0으로 고르는, 1로 고르는 ...... 256으로 고르는 시간을 각각 계산해서 비교해주는 식으로 풀었다.

위 방법을 brute force (브루트포스) 무차별 대입이라고 한다.

 

먼저 높이의 개수를 저장하는 hight 배열을 만들었다. 예를 들어

이런 땅이 있다면 hight[1] =2, hight[5]=2, hight[7]=5 이렇게 되는것이다.

이런식으로 저장하는 이유는 이 땅을 6으로 만들려고 한다면 6을 기준으로 작은 높이들은 쌓아올려주는데 이때의 블록 개수는 쌓아올리려는 쌓아올리려는 시작 높이와 목표 높이의 차 * 그 높이의 개수이다. 이때 쌓아올리려는 시작 높이는 목표 높이보다 작은 모든 높이로 계산해주면 된다. 그렇게 계산한 블록 수는 바로 목표 높이까지 쌓는 시간이 된다.

깎으려는 블록 수는 시작 높이와 목표 높이의 차 * 그 높이의 개수로 7로 예를 들면 (7-6)*5 이다.

그리고 깎는 시간은 블록 1개당 2초가 걸리기 때문에 2를 곱해주면 깎는데 걸리는 시간이 된다.

이렇게 해서 모든 높이들을 목표 높이와 비교해서 걸리는 시간을 구해준 후 마지막으로 깎은 블록과 원래 있던 블록 b를 더해서 쌓아올린 블록보다 작거나 같으면 가능한 땅 고르기이고 만약 쌓아올린 블록이 더 많다면 없는 블록을 쓴것이기 때문에 정답이 될 수 없는 값 이므로 비교대상에서 제외 시켜준다. 이렇게 목표 높이를 0부터 256까지 반복해주면 문제는 해결 된다. 답이 여러 개 있다면 땅 높이가 가장 높은 것을 답으로 하는데 우리는 for문으로 높이를 목표 높이를 0부터 256까지 순차적으로 가기 때문에 같은 시간이 걸리면 그 값을 그냥 저장해주면된다.

 

전체 코드

#include <iostream>
#include <string.h>
using namespace std;
int main(){
    long long n, m, b;
    int a;
    cin >> n >> m >> b;
 
    int hight[257];
    memset(hight, 0, sizeof(hight));
    for (int i = 0; i < n;i++){
        for (int j = 0; j < m;j++){
            cin >> a;
            hight[a]++; // 높이의 개수 저장
        }
    }
    long long ans = 999999999;
    long long sum_block, sub_block;
    long long time;
    int ans2 = 0;
 
    for (int i = 0; i < 257;i++){ //i는 만들 땅의 높이
        sum_block = 0;
        sub_block = 0;
 
        for (int j = 0; j < i;j++){
            sum_block += (i - j) * hight[j]; // 만들 땅의 높이 보다 작음 -> 쌓아올려야함 -> 
            //블록 수 = 만들 땅과의 높이 차 * 높이의 개수
        }
        for (int k = i + 1; k < 257;k++){ // 만들 땅의 높이 보다 높음
            sub_block += (k - i) * hight[k];
            //블록 수 = 만들 땅과의 높이 차 * 높이의 개수
        }
        if(sum_block<=sub_block+b){ 
            //깎은 블록 + 원래 있던 블록이 많거나 같아야 블록을 쌓을 수 있음
            time = sum_block + sub_block * 2;
            if(ans >= time){ // 시간이 더 적게 걸리거나 같으면 값 저장
            //0부터 256까지 점점 목표 높이를 높아서 검사하기 때문에 자동으로 높은 값 저장
                ans = time; //걸리는 시간 
                ans2 = i; // 땅을 고른 높이
            }
        }
 
    }
    cout << ans << " " << ans2;
    return 0;
}

 사용 알고리즘 : 브루트 포스(brute force)

 

yea!