백준, BOJ, 18111번 C++ [CPP]

1초지만 은근히 숫자가 적어서 해볼만하다 생각한 문제

 

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

 

---

처음에 든 생각은..

다 조사해볼 생각은 안했고..

어떠한 것이 가장 최소 시간을 가질지 계산해보기로 했다.

당연히 모든 블럭에 대한 평균 높이로 만드는 것이 최소시간이 걸릴 것이라 생각했다.

 

뭐 시간이 달라서 틀린 생각이 되었고 또한 답이 같을 경우 높이가 높은 것 까지 조사해봐야 했으므로

전수조사를 해야했다. brute force란다.

 

처음에 틀린 풀이를 보자

#include <iostream>
#include <cmath>

using namespace std;

int N, M, B; //(1 ≤ M, N ≤ 500, 0 ≤ B ≤ 6.4 × 10^7)
int minh = 257;
int maxh = -1;
int map[501][501];

void init() {
    ios::sync_with_stdio(0);
    cin.tie(0);
}

//1번 작업은 2초가 걸리며, 2번 작업은 1초가 걸린다.

int main() {
    init();

    int anst = 9999999;
    int ansh = 0;

    cin >> N >> M >> B;


    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> map[i][j];
            if (minh >= map[i][j]) {
                minh = map[i][j];
            }
            if (maxh <= map[i][j]) {
                maxh = map[i][j];
            }
        }
    }

    //최저 높이부터 최고 높이까지 조사
    //다 만들어보고 최소 시간 중 가장 높은 높이 출력

    for (int h = minh; h <= maxh; h++) {
        int t = 0;
        int add = 0; // 쌓아야 할 블럭
        int sub = 0; // 깎아야 할 블럭

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                int block = h - map[i][j]; // 해당 높이까지 필요한 블럭 양수면 블럭을 쌓아야하고 음수면 캐내야함
                if(block < 0) {
                    sub += abs(block);
                }
                else if (block > 0) {
                    add += block;
                }
                else {
                    continue;
                }
            }
        }

        if (add > sub + B) {
            t = 999999;
            continue;
        }
        else {
            t = add * 1 + sub * 2;

        }


        if (t <= anst ) {
            anst = t;
            ansh = h;
        }
    }

    cout << anst << " " << ansh;






}

 

 

맞아보이지만 틀렸다.

 

맞은 풀이를 보자

#include <iostream>
#include <cmath>

using namespace std;

int N, M, B; //(1 ≤ M, N ≤ 500, 0 ≤ B ≤ 6.4 × 10^7)
int minh = 257;
int maxh = -1;
int map[501][501];

void init() {
    ios::sync_with_stdio(0);
    cin.tie(0);
}

//1번 작업은 2초가 걸리며, 2번 작업은 1초가 걸린다.

int main() {
    init();

    int anst = 1e9;
    int ansh = -1;

    cin >> N >> M >> B;


    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> map[i][j];
            if (minh >= map[i][j]) {
                minh = map[i][j];
            }
            if (maxh <= map[i][j]) {
                maxh = map[i][j];
            }
        }
    }

    //최저 높이부터 최고 높이까지 조사
    //다 만들어보고 최소 시간 중 가장 높은 높이 출력

    for (int h = minh; h <= maxh; h++) {
        int t = 0;
        int add = 0; // 쌓아야 할 블럭
        int sub = 0; // 깎아야 할 블럭

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                int block = h - map[i][j]; // 해당 높이까지 필요한 블럭 양수면 블럭을 쌓아야하고 음수면 캐내야함
                if (block < 0) {
                    sub += abs(block);
                }
                else {
                    add += block;
                }
            }
        }

        if (add <= sub + B) {
            t = add + sub * 2;
            if (t <= anst) {
                anst = t;
                ansh = h;
            }
        }


    }

    cout << anst << " " << ansh;






}

 

t를 갱신하는 조건이 달랐다.

어차피 계산이 될 때만 t를 갱신하면 될 것을..

 

마지막에

해당 층으로 만들기 위해 더해야할 블럭, 빼야 할 블럭, 현재 가지고 있는 블럭의 수를 총합하여

더해야할 개수가 > 뺀 개수 + 가지고 있는 블럭이 된다면

해당 높이로는 평평하게 만들 수 없다.

 

오랜만에 다시 시작하니까 

감떨어졌네 ㅎ