[18111] - 마인크래프트

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

18111번: 마인크래프트

접근 방법

처음 문제를 접했을 때 높이의 분포가 가장 많은 걸 기준으로 파고,놓기를 하려했다가 최소 시간이 아닐 수 있어 포기.

생각해보니 높이가 0~256까지 있으니 기준을 잡고 그 높이로 전체 탐색을 돌리면 되겠다 싶어서 구현.

 

문제 풀이

• 기준을 0~256까지 잡고 탐색
• 높이가 기준보다 높으면 땅을 파고, 낮으면 땅을 놓아서 dig, put 변수에 더하기
• 전체를 평평하게 했으면 인벤에 있는 흙+판 흙이 놓은 흙보다 크거나 같으면 시간과 높이 갱신
  • 이 때, 순서 대로 땅을 파고 놓는게 아니니 다끝나고 계산을 해도 됨.
• 최소 시간의 최대 높이를 비교, 반복문 탈출 후 출력

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Baekjoon.Practice
{
    class _18111
    {
        static void Main_18111(string[] args)
        {
            int[] n = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            int have = n[2]; //가진 흙

            int[][] arr = new int[n[0]][];
            for(int i = 0; i< n[0]; i++)
                arr[i] = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

            int time = -1;
            int high = -1;
            for(int earth = 0; earth<257; earth++)
            {
                int dig = 0; //파기
                int put = 0; //놓기

                for(int i = 0; i < n[0]; i++)
                {
                    for(int j = 0; j < n[1]; j++)
                    {
                        if (arr[i][j] > earth)
                            dig += (arr[i][j] - earth);
                        else if (arr[i][j] < earth)
                            put += (earth - arr[i][j]);
                    }
                }

                if(have + dig >= put)
                {
                    if (time == -1)
                        time = dig * 2 + put;

                    if(time >= dig * 2 + put)
                    {
                        time = dig * 2 + put;
                        high = Math.Max(high, earth);
                    }
                }
            }

            Console.WriteLine($"{time} {high}");
        }
    }
}