Written by JS970
on February 12, 2023

18111 - 마인크래프트

난이도: 실버 2
날짜: 2023년 2월 12일
상태: Correct
추가 검토 여부: No
알고리즘 : 브루트포스

solution

주어진 입력 범위에 대한 모든 경우의 수를 탐색한다고 했을 때, 500 * 500 * 256 = 64,000,000이므로 완전 탐색을 해도 시간은 충분하다.
문제에서 놓치기 쉬운 조건들이 많은 편이었다.
- 같은 시간이 걸릴 경우 가장 높은 높이를 가지는 경우를 정답으로 출력할 것
- 블록의 개수가 부족할 경우에는 블록을 쌓을 수 없고 블록을 캐는 것만 가능하다.
- 블록을 캐면 전체 블록의 수가 그만큼 증가한다.
숨은 조건도 있었다.
- 블록을 쌓거나 캐는 순서는 정해진 바가 없다. 탐색 연산 중 일시적으로 전체 블록이 0 미만으로 떨어지더라도 순서를 조정하여 바로잡을 수 있다.
- 구현에서는 이중 for문을 사용하여 범위 안에서 가질 수 있는 모든 높이 값에 대해 걸리는 시간을 탐색했다. 이때 입력값을 저장하는 배열을 내림차순으로 정렬하여 블록을 먼저 캐고 난 후 쌓는 순서로 탐색하도록 설정했다. 이렇게 하면 전체 블록이 0미만으로 떨어질 경우 100% 문제 조건에 부합하지 않는다.
혹시 모를 시간 초과를 방지하기 위해 입력값으로 주어지는 높이의 최솟값과 최댓값을 구하여 탐색 범위를 한정했다.
블록 값이 음수로 떨어진 경우에 대해서 쓰레기 값이 결과값 pair에 저장되는 것을 막기 위해 vaild라는 bool변수를 추가했다.

code

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M, B;
    cin >> N >> M >> B;
    int * arr = new int[N*M];
    int max_arg = -1;
    int min_arg = 257;
    for(int i = 0; i < N*M; i++)
    {
        cin >> arr[i];
        max_arg = (max_arg < arr[i]) ? arr[i] : max_arg;
        min_arg = (min_arg > arr[i]) ? arr[i] : min_arg;
    }
    sort(arr, arr+N*M, greater<int>());
    
    int time = 0;
    int block = B;
    bool valid = true;
    pair<int, int> ans;
    ans.first = -1;
    for(int i = min_arg; i <= max_arg; i++)
    {
        block = B;
        time = 0;
        valid = true;
        for(int j = 0; j < N*M; j++)
        {
            if(arr[j] >= i)
            {
                time += (arr[j]-i) * 2;
                block += (arr[j]-i);
            }
            else
            {
                if(i - arr[j] > block) valid = false;
                else
                {
                    time += (i-arr[j]) * 1;
                    block -= (i-arr[j]);
                }
            }
        }
        if(ans.first == -1 && valid)
        {
            ans.first = time;
            ans.second = i;
        }
        else if(ans.first > time && valid)
        {
            ans.first = time;
            ans.second = i;
        }
        else if(ans.first == time && valid)
        {
            ans.first = time;
            ans.second = (i < ans.second) ? ans.second : i;
        }
    }

    cout << ans.first << " " << ans.second << endl;

    return 0;
}

ref

18111번: 마인크래프트

Top