문제 링크

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

문제 풀이

해당 문제는 2차원 배열의 숫자를 고르게 만드는 데 걸리는 최소 시간과, 그 때의 숫자를 구하는 문제이다.

처음에는 나열된 숫자의 중앙값을 구해 해당 값에서 부터 시작해서 만약 블록이 모자르면 target값을 하나씩 감소시켜서 해결할 예정이었지만, 구현하다보니 중앙값보다 큰 수가 답이 되는 경우도 발견했다.

이진 탐색으로 해결해볼까 하다가, 일단 문제의 분류대로 구현하기 위해 숫자의 최댓값부터 최솟값까지 하나씩 감소시켜가며 문제를 풀었다.

해당 문제에서 주의해서 구현해야할 사항은 다음 두 가지가 있다.

1. 인벤토리에 있는, 그리고 인벤토리에 채울 수 있는 블록의 개수를 고려할 것
2. 땅을 고르게 하는 최솟값이 여러개인 숫자가 있다면, 그 중에서 큰 값을 출력할 것

위 두 가지만 고려한다면 금방 풀 수 있다. 2번째 조건은 최댓값부터 시작하면 자연스럽게 지켜지는 조건이다.

코드

C++

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <climits>
#include <queue>
#include <list>
#include <stack>

using namespace std;

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, -1, 1};

const int MAX_INVEN = 64 * 1000 * 1000;
int m, n, inven;

vector<vector<int>> ground;
vector<int> cache;


bool checkGround(int target) {
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (ground[i][j] != target)
                return false;
        }
    }
    return true;
} 

bool checkInven(int target) {
    int sum = 0;
    int need = 0;
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (ground[i][j] > target) {
                sum += ground[i][j] - target;
            } else {
                need += target - ground[i][j];
            }
        }
    }

    sum += inven;

    if (sum > MAX_INVEN || need > MAX_INVEN) {
        return false;
    } else if (need <= sum) {
        return true;
    } else {
        return false;
    }
}

int main() {

    ios_base::sync_with_stdio(false);
    cout.tie(nullptr);
    cin.tie(nullptr);

    cin >> m >> n >> inven;
    
    ground = vector(m, vector<int>(n, 0));

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

    int target = 257;
    int minTime = 500 * 500 * 255 * 2, maxTarget = target;
    while (target > 0) {

        target -= 1;
        int time = 0;
        
        // invent check
        if (!checkInven(target))
            continue;

        // 땅 고르기 작업
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int differ = target - ground[i][j];
                if (differ > 0) { // target > ground[i][j]
                    time += differ;
                } else if (differ < 0) { // target < ground[i][j]
                    time += (2 * abs(differ));
                }
            }
        }

        // minTime 갱신
        if (time < minTime) {
            minTime = time;
            maxTarget = target;
        }
    }
    cout << minTime << " " << maxTarget;
    return 0;
}

Python