[C] 백준 | 18111번 코드 - *마인크래프트

>문제

> 핵심

브루트포스 알고리즘

(모든 경우를 다 따져보는 방법)

>풀이과정

아.. 어렵다

혼자 끙끙 생각하다가 도저히 생각이 안나서 다른사람이 쓴 아이디어를 보고나서야 풀었다..

풀고나서야 그렇게 어려운 문제가 아니었다는걸 깨달았다.. 코딩은 나의 길이 아닌가

 

내가 생각한 방법

1. 블록의 높이를 입력받으면서 가장 높은 max, 가장 낮은 min 값을 찾는다.

2. max층부터 min층까지 층층이 탐색하면서,

2-1. 현재 높이에서 구멍이 몇칸 뚫려있는지 구하고

2-2. 인벤토리에 있는 블럭으로 그 구멍을 다 메꿀 수 있으면 메꾸고 break.

2-3. 메꿀 수 없으면 한층 더 파고 내려가기

3. 그렇게 돌면서 모든 블럭이 평평하게 맞춰진다면 break 후 총 걸린시간 출력..

 

하는 구조를 생각했었는데,

이건 해당 층에서 메꾸는게 빠른지 채우는게 빠른지 다른 경우와 비교할 수도 없고, 

블록을 메꾸는 경우보다 블록을 파는 경우 더 시간이 빠를 수도 있는데 그건 고려할 수 없다는 점에서 틀렸다..

 

** 그래서 수정한 방법

1. 블록의 높이를 입력받으면서 max와 min값을 찾는다. 이후 max층부터 min층까지 반복문 시작

 

2-1. 현재 층과 블록의 높이차를 계산 ( diff = height[j][k]-i ), 

-> time = 0

-> b = inventory (갖고있는 블럭의 수)

 

2-2. diff > 0 이라면 현재 층보다 블록이 높게 쌓여있다는 것으로 블록을 파야한다. 

-> time = time + ( diff * 2 )   (* 한 블록을 파는데는 2초가 걸리므로)

-> b = b + diff   (* 파낸 블록은 인벤토리에 넣는다)

 

2-3. diff < 0 이라면 현재 층보다 블록이 낮게 파져있다는 것으로 블록을 메꿔야한다.

-> time = time - diff    (* diff < 0이므로 뺄셈을 해야함!!)

-> b = b + diff    (* 메꿀때마다 블록을 소모, diff < 0이므로 덧셈을 해야함!)

 

3. b >= 0 이라면, 현재 소요된 시간 time과, 모든 경우 중 가장 빠른 시간을 저장하는 min_time을 비교해 더 빠른 시간의 값을 min_time에 저장   (* b < 0인 경우는 불가능한 경우이므로 X)

 

4. 위의 과정을 max부터 min까지 반복.

 

5. 모든 경우의 수 중 가장 빠른시간, min_time을 출력.

 

>깨달은점

코딩은 해도해도 부족하고 모르는게 너무 많은 것 같다.

노력만으로 재능을 이길 수 있을까 모르겠다.

그래도 노력은 해야겠다. 뭐라도 남는건 있겠지

>코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int main()
{
    int sero, garo, inventory, i, j, k, max, min;
    int** height;

    scanf("%d %d %d", &sero, &garo, &inventory);

    // int[]을 배열로 갖는 배열
    height = (int**)malloc(sizeof(int*) * sero);
    for (i = 0; i < sero; i++)
    {
        height[i] = (int*)malloc(sizeof(int) * garo);
    }

    max = 0, min = 256;
    for (i = 0; i < sero; i++)
    {
        for (j = 0; j < garo; j++)
        {
            scanf(" %d", &height[i][j]);
            if (height[i][j] < min)
            {
                min = height[i][j];
            }
            else if (height[i][j] > max)
            {
                max = height[i][j];
            }
        }
    }

    int time = 0, min_time = INT_MAX, block_height = 256;

    // 최고높이에서부터 최저높이까지 층층이 탐색
    for (i = max; i >= min; i--)
    {
        int b = inventory;
        time = 0;

        for (j = 0; j < sero; j++)
        {
            for (k = 0; k < garo; k++)
            {
                int diff = height[j][k] - i;
 
                if (diff < 0)
                {
                    time -= diff;
                    b += diff;
                }
                else if (diff > 0)
                {
                    time += diff * 2;
                    b += diff;
                }
            }
        }
        // b < 0인 경우는 불가능한 경우.
        if (b >= 0)
        {
            if (time < min_time)
            {
                min_time = time;
                block_height = i;
            }
        }
    }

    printf("%d %d\n", min_time, block_height);

    for (i = 0; i < sero; i++)
    {
        free(height[i]);
    }
    free(height);

    return 0;
}