본문 바로가기
코딩테스트/백준

[백준] 18111번 - 마인크래프트 (실버 2)

by Hwan,. 2022. 3. 14.
728x90
반응형

1. 문제

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

 

18111번: 마인크래프트

팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게

www.acmicpc.net

2. 접근 방식

  • 1차 : 전체 블록의 평균(높이)을 구해서 해당 높이까지 블록을 맞춰주는 로직 작성 -> 틀림
  • 2차 : 0~가장 큰 높이의 블록을 기준으로 각 케이스를 계산하여 가장 시간이 빠른 경우 선택 -> 1%에서 틀림
  • 3차 : 위와 동일하지만 블록을 먼저 다 회수하고 설치 진행 -> 시간초과
  • 4차 : 제거할 블록과 쌓을 블록의 개수를 구하고 시간을 나중에 구함 -> 통과

3. 반례

// 1 64
3 4 1
64 64 64 64
64 64 64 64
64 64 64 63

// 22 63
3 4 0
64 64 64 64
64 64 64 64
64 64 64 63

// 2 0
3 4 99
0 0 0 0
0 0 0 0
0 0 0 1

// 2 1
1 3 68
0 0 1

// 250 35
3 4 11
29 51 54 44
22 44 32 62
25 38 16 2

// 355 32 
4 4 36
15 43 61 21
19 33 31 55
48 63 1 30
31 28 3 8

// 0 0
1 1 0
0

// 768 128
2 2 0
256 256
0 0

// 879 10
7 7 6000
30 21 48 55 1 1 4
0 0 0 0 0 0 0
15 4 4 4 4 4 8
20 40 60 10 20 30 2
1 1 1 1 1 1 9
24 12 33 7 14 25 3
3 3 3 3 3 3 32

// 350 40
2 2 35
20 10
190 40

// 290 170
2 2 68
120 90
250 170

 

4. 코드

  • 1차 코드 : 동일한 시간일 경우 높은 높이 조건을 충족하지 못함. ( + 틀린 케이스 존재)
#include<iostream>
#include<cmath>

using namespace std;

int main() {
    int n, m, inventory, height, time = 0;
    double sum = 0;

    cin >> n >> m >> inventory;

    // 맵 입력
    int** map = new int*[n];
    for (int i = 0; i < n; i++) {
        map[i] = new int[m];
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
            sum += map[i][j];
        }
    }

    // 전체 높이 결정 (인벤토리 기준)
    if (inventory > 0) {
        height = round(sum / (n * m));
    }
    else {
        height = floor(sum / (n * m));
    }
    
    // 땅 다듬기
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (map[i][j] == height)
                continue;

            if (map[i][j] > height) {
                time += 2;
                map[i][j] -= 1;
                inventory++;
            }
            else {
                time += 1;
                map[i][j] += 1;
                inventory--;
            }

        }
    }

    cout << time << " " << height << "\n";
    
    return 0;
}

 

  • 2차 코드 : 틀린 케이스 존재 (앞에부터 가져와서 쌓기 때문에 블록이 부족한 경우 발생)
#include<iostream>
#include<cmath>

using namespace std;

// 현재 맵에서 입력된 높이까지 얼마의 시간이 걸리는지 반환
int func_18111_getTime(int height, int n, int m, int inventory, int **map) {
    int time = 0, tmp_map;
    bool flag = true;

    // map 전체 스캔
    for (int i = 0; i < n && flag; i++) {
        for (int j = 0; j < m && flag; j++) {
            tmp_map = map[i][j];

            if (tmp_map == height)
                continue;
			
            // 현재 블록의 높이가 원하는 높이보다 높으면 블록 회수
            if (tmp_map > height) {
                while (tmp_map != height) {
                    time += 2;
                    tmp_map -= 1;
                    inventory++;
                }
            }
            else {
                // 블록 설치 (인벤토리가 부족하면 flag == false
                while (tmp_map != height) {
                    if (inventory > 0) { 
                        inventory--; 
                    }
                    else {
                        flag = false;
                    }

                    if (!flag) 
                        break;

                    time += 1;
                    tmp_map += 1;
                }

                if (!flag || tmp_map != height) {
                    flag = false;
                    break;
                }
            }

        }
    }
    
    // flag 가 false 면 time 초기화
    if (!flag) {
        time = 0;
    }

    return time;
}

int main() {
    int n, m, inventory, height=-1, time = 0, tmp, min = 2100000000, max=0;
    double sum = 0;

    cin >> n >> m >> inventory;

	// 맵 정보 입력 및 블록 최대값 구하기
    int** map = new int* [n];
    for (int i = 0; i < n; i++) {
        map[i] = new int[m];
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
            if (max < map[i][j]) {
                max = map[i][j];
            }
        }
    }
    
    // 0 ~ 블록 최대 값 중 시간이 가장 빠르고, 높이가 높은 값 찾기
    for (int i = 0; i <= max; i++) {
        tmp = func_18111_getTime(i, n, m, inventory, map);

        if (min >= tmp && tmp > 0) {
            if (min == tmp && height > i) continue;
            min = tmp;
            height = i;
        }
    }

    // 찾을 수 없으면 0으로 초기화
    if (min == 2100000000 || height == -1) {
        min = 0;
        height = 0;
    }
    
    cout << min << " " << height << "\n";
    
    return 0;
}

 

  • 3차 코드 : 입력 높이(height)보다 높은 블록들 먼저 회수하고, 낮은 블록 쌓기
#include<iostream>
#include<cmath>

using namespace std;

int func_18111_getTime(int height, int n, int m, int inventory, int **map) {
    int time = 0, tmp_map;
    bool flag = true;

    // 블록 회수 (높이 낮추기)
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            tmp_map = map[i][j];

            if (tmp_map == height)
                continue;
            
            if (tmp_map > height) {
                while (tmp_map != height) {
                    time += 2;
                    tmp_map -= 1;
                    inventory++;
                }
            }
        }
    }
    
    // 블록 설치 (부족하면 flag == false)
    for (int i = 0; i < n && flag; i++) {
        for (int j = 0; j < m && flag; j++) {
            tmp_map = map[i][j];

            if (tmp_map == height)
                continue;

            if (tmp_map < height) {
                while (tmp_map != height) {
                    if (inventory > 0) {
                        inventory--;
                    }
                    else {
                        flag = false;
                    }

                    if (!flag)
                        break;

                    time += 1;
                    tmp_map += 1;
                }

                if (!flag || tmp_map != height) {
                    flag = false;
                    break;
                }
            }
        }
    }

    if (!flag) {
        time = 0;
    }

    return time;
}

int main() {
    int n, m, inventory, height=-1, time = 0, tmp, min = 2100000000, max=0;
    double sum = 0;

    cin >> n >> m >> inventory;

    int** map = new int* [n];
    for (int i = 0; i < n; i++) {
        map[i] = new int[m];
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
            if (max < map[i][j]) {
                max = map[i][j];
            }
        }
    }
    
    for (int i = 0; i <= max; i++) {
        tmp = func_18111_getTime(i, n, m, inventory, map);

        if (min >= tmp && tmp > 0) {
            if (min == tmp && height > i) continue;
            min = tmp;
            height = i;
        }
    }

    if (min == 2100000000 || height == -1) {
        min = 0;
        height = 0;
    }
    
    cout << min << " " << height << "\n";
    
    return 0;
}

 

  • 4차 코드 : 통과
#include<iostream>
#include<cmath>

using namespace std;

int main() {
    int n, m, inventory, min = 2100000000, max = 0;
    int height = -1, time = 0, tmp_block, time_min= 2100000000;
    double sum = 0;

    cin >> n >> m >> inventory;

    // 맵 입력
    int** map = new int* [n];
    for (int i = 0; i < n; i++) {
        map[i] = new int[m];
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];

            if (max < map[i][j]) {
                max = map[i][j];
            }

            if (min > map[i][j]) {
                min = map[i][j];
            }
        }
    }

    int build_block, remove_block;

    // 맵의 최소 블록 높이부터 가장 높은 블록까지 반복
    for (int h = min; h <= max; h++) {
        build_block = 0;
        remove_block = 0;

        // h에서의 회수할 블록, 설치할 블록 개수 구하기
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                tmp_block = map[i][j];

                // 현재 블록이 h보다 낮으면 설치할 블록 개수 누적
                if (h > tmp_block) {
                    build_block += h - tmp_block;
                }

                // 현재 블록이 h 보다 높으면 회수할 블록 개수 누적
                if (h < tmp_block) {
                    remove_block += tmp_block - h;
                }
            }
        }

        // 설치할 블록 개수가 인벤토리와 회수한 블록의합보다 부족한지 검사
        if (build_block <= remove_block + inventory) {
            time = remove_block * 2 + build_block;

            if (time_min >= time) {
                if (height > h) continue;
                time_min = time;
                height = h;
            }
        }
    }

    cout << time_min << " " << height << "\n";
    
    return 0;
}

5. 결과

728x90
반응형
저작자표시 비영리 동일조건

'코딩테스트 > 백준' 카테고리의 다른 글

[백준] 10026번 - 적록색약 (골드 5)  (0) 2022.04.04
[백준] 10773번 - 제로 (실버 4)  (0) 2022.03.15
[백준] 15829번 - Hashing (브론즈 2)  (0) 2022.03.15
[백준] 1009번 - 분산처리 (브론즈 3)  (0) 2022.03.10
[백준] 삼성 SW 역량 테스트 기출 문제 (작성중)  (0) 2022.02.22
[백준] 단계별로 풀어보기 > 그리디 알고리즘 (c++)  (0) 2022.02.20

관련글

댓글

티스토리툴바