[C#] 백준 2805번 문제풀이

안녕하세요.

C#을 이용한 백준 2805번 풀이를 해보도록 하겠습니다.

 

해당 문제는 상근이가 필요한 나무를 일정량 얻기 위해 나무가 일자로 서있는 곳에서 톱의 높이를 조절한 후 나무를 얻어야 하지만, 환경파괴를 최소화 해야하는 문제입니다.

 

예제 입력

4 7
20 15 10 17

예제 출력

15

 

첫번째 줄에 나무의 수(N)가 주어지고, 잇달아 필요한 나무의 총 길이(M)가 주어집니다.

처음 문제를 제출할때는 단순히 반복문을 사용해서 길이를 하나씩 빼는 방식으로 제출해보았지만 당연하게도 시간초과가 났습니다.

저는 이 문제를 해결하기 위해 기존 선형탐색 기법보다 이진탐색 기법을 사용하기로 했습니다.

 

이진탐색의 원리는 간단합니다. 탐색할 범위를 계속 반씩 줄여나가며 답을 더 효율적으로, 빨리 찾을 수 있게 하는 기법입니다.

 int[] nm = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
 List<int> trees = Array.ConvertAll(Console.ReadLine().Split(), int.Parse).ToList();
 int N = nm[0];
 int M = nm[1];
 trees.Sort();

우선 입력을 받아옵니다.

나무의 개수, 필요한 나무의 길이, 나무의 높이를 배열로 받아왔습니다.

나무의 개수(N)와 필요한 나무의 길이(M)은 각각 N,M으로 분리해주고, 나무 배열은 정렬해줍니다.

 

int MaxHeight = trees.Max();
int MinHeight = 0;
int result = 0;

톱의 최고높이, 최소높이를 저장할 변수와 답을 저장할 result 변수를 만들어주었습니다.

 

while(MinHeight <= MaxHeight)
{
    int mid = (MaxHeight + MinHeight) / 2; // 중간값
    long TreeLength = 0; // 잘라낸 나무 길이 저장
    for (int i = 0; i < N; i++)
    {
        if (trees[i] > mid)
        {
            TreeLength += trees[i] - mid;
        }
    }
    if (TreeLength >= M)
    {
        result = mid;
        MinHeight = mid + 1;
    }
    else
    {
        MaxHeight = mid - 1;
    }
}

반복문 안에 중간값을 저장할 mid 변수를 만들어주고 식을 작성하였습니다.

이 mid가 이진탐색의 핵심이 되는 변수입니다.

또한 잘라낸 나무의 길이 합을 저장할 TreeLength 변수를 만들어주었습니다.

 

이제 for 반복문을 돌려 톱의 길이가 나무길이보다 밑에있다면 나무를 잘라내고, 잘린 나무의 길이를 TreeLength 에 모두 저장해줍니다. for 반복문이 끝난 후 TreeLength 에는 잘려나간 나무의 길이가 모두 저장되었습니다.

 

그 후에 M(필요한 나무의 총 길이) 이 잘려나간 나무의 총 합과 같거나 작은지, 즉 필요한 나무 길이 조건을 충족했는지 검사합니다.
참이라면, result 답 변수에 mid(중간) 값을 저장합니다. 그리고 MinHeight(최소 톱 높이) 에 mid + 1을 저장하여 다음 탐색에는 반을 줄인 범위만 탐색 할 수 있도록 합니다. 거짓이라면, MaxHeight(최대 톱 높이) 에 mid - 1을 한 값을 저장하여 똑같이 반을 줄인 범위를 검사할 수 있도록 합니다.

 

이렇게 MinHeight 가 MaxHeight 보다 작거나 같을동안 위 동작을 반복하면 result에는 최대 톱 높이가 저장됩니다.

 

Console.WriteLine(result);

마지막으로 result를 뽑아내면, 성공적으로 답이 출력됩니다. 👍

 

전체코드

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

namespace aa
{
    class aaa
    {
        public static void Main(string[] args)
        {
            // 나무자르기
            int[] nm = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            List<int> trees = Array.ConvertAll(Console.ReadLine().Split(), int.Parse).ToList();
            int N = nm[0];
            int M = nm[1]; // 필요한 나무 길이
            trees.Sort();

            int MaxHeight = trees.Max();
            int MinHeight = 0;

            int result = 0;

            while(MinHeight <= MaxHeight)
            {
                int mid = (MaxHeight + MinHeight) / 2; // 중간값
                long TreeLength = 0; // 잘라낸 나무 길이 저장
                for (int i = 0; i < N; i++)
                {
                    if (trees[i] > mid)
                    {
                        TreeLength += trees[i] - mid;
                    }
                }
                if (TreeLength >= M)
                {
                    result = mid;
                    MinHeight = mid + 1;
                }
                else
                {
                    MaxHeight = mid - 1;
                }
            }

            Console.WriteLine(result);
        }
    }
}