[백준] 2805 나무 자르기(C#)

문제

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

2805번: 나무 자르기

코드

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

namespace dongsik
{
    class Algorithm
    {
        static void Main(string[] str)
        {
            int[] input = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
            int n = input[0];
            int m = input[1];

            int[] tree = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);

            long end = 0;
            long start = 0;
            
            foreach(int t in tree)
            {
                if(end < t) { end = t; }
            }

            while(start <= end)
            {
                long mid = (start + end)/2;
                long sum = 0;

                for(int i = 0; i < n; i++)
                {
                    if(tree[i] > mid)
                    {
                        sum += tree[i] - mid;
                    }
                }

                if(sum >= m) { start = mid + 1; }
                else { end = mid - 1; }
            }
            
            // 길이
            Console.Write(end);
        }
    }
}

고민

노션에 이런 고민들을 해봤다.. 그리고 계속해서 정답이 틀렸는데, 이유가

 

1. return은 mid가 아니라 end다.

2. long타입으로 선언

 

왜 end인지는 뤼튼이 알려줬다.

어머! 얘. 내가 알려줄게 너가 말하려던게 이거 맞지? 이건 말이야~~ 백준 2805 문제는 이진 탐색을 활용하여 풀 수 있는 문제야. 코드를 보니 대체적으로 잘 작성한 것 같아. 하지만 한 가지 문제가 있어. 문제는 이진 탐색이 끝나고 난 후의 결과 출력 부분이야. `Console.Write(mid);`라고 써서 마지막으로 계산한 mid 값을 출력하도록 했는데, 실제로는 mid 값이 아니라 end 값을 출력해야 해. 왜냐하면 이진 탐색의 과정에서 mid 값을 사용해 나무의 높이를 계산하고, 그 결과가 필요한 나무의 길이보다 크거나 같으면 시작점을 mid+1로 옮기는 과정을 거치잖아? 그런데 만약 필요한 나무의 길이와 정확히 일치하는 높이를 찾지 못하고, 그보다 조금 더 많이 잘랐을 경우에는 mid 값이 실제로 사용 가능한 최대 높이보다 1이 더 큰 상태로 종료되게 돼. 그래서 맞는 값을 출력하려면 `Console.Write(end);`로 바꿔야 해. 그러면 이진 탐색이 끝났을 때의 최대 높이를 올바르게 출력할 수 있을거야.

음.. 그렇다면 while문에 조건을 넣는다면?

 

            while(start <= end)
            {
                long mid = (start + end)/2;
                long sum = 0;

                for(int i = 0; i < n; i++)
                {
                    if(tree[i] > mid)
                    {
                        sum += tree[i] - mid;
                    }
                }
                
                if(mid == m) { result = mid; break; }

                if(sum >= m) { start = mid + 1; }
                else { end = mid - 1; }
            }
            
            // 길이
            Console.Write(result);

mid는 정답이 될 수 없는 것인지 고민하다가 위처럼 코드를 짰다. 하지만 실패

문제는 if(mid == m) { result = mid; break; } 이 부분이야. 이 코드는 이진 탐색의 중간 값(mid)이 목표로 하는 나무의 길이(m)과 같을 경우, 즉시 이진 탐색을 종료하도록 설계되어 있어.

하지만 이렇게 하면 문제가 생겨. 이 문제에서 나무의 길이와 중간값이 같다는 것이 곧 최적의 해라는 것을 보장하지 않아. 왜냐하면 mid 값이 m과 같더라도, 더 큰 mid 값에서도 m 이상의 나무를 얻을 수 있을지도 모르니까. 따라서 mid 값이 m과 같을 때 바로 종료하면 그보다 높은 높이에서 얻을 수 있는 결과를 놓칠 수 있어.

그렇다고 하네요... 

 

이진탐색을 무조건 mid에만 포커스를 두었는데, 실제로는 end였다니.. 너무 충격적이라서 기억에 오래 갈 거 같다.