16. 2805번 나무 자르기

 

2805번: 나무 자르기

이분탐색 문제

[알고리즘] 이분 탐색

나무를 입력받고 left(0), right(나무 중 최대 길이값), mid(왼쪽, 오른쪽 평균값) 을 구해준 뒤

평균값으로 나무들을 다 자름

 

1. 자른 나무의 길이의 합 (sum) >= 가져갈 나무의 길이(M) 

2. 자른 나무의 길이의 합 (sum) < 가져갈 나무의 길이(M)  

 

이렇게 나눠서 생각할 수 있었음

 

1번일 경우 left = mid +1 해주고 정답값에 mid를 넣어줌

2번일 경우 right = mid -1 해주면서

 

탐색 범위를 좁혀감

 

left가 right보다 커지면 탐색 종료고 값을 출력함 

 

처음에 틀려서 반례 찾다가 입력값이 워낙 커서 long으로 안하면 스택오버플로우 난다고 봐서

나무 길이 입력값은 다 long으로 바꿈 (int64.parse 써야함  int32.parse ㄴㄴ)

 

이분탐색이 낯선 거 빼곤 아주 많이 어렵진 않았음..

 

*

4 10

1 4 5 7

반례로 예시 말고 이것도 입력해보기 (답은 2)

 

 

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

namespace _2805
{
    public class Tree
    {
        public long length;

        public Tree(long length)
        {
            this.length = length;
        }
    }


    class Program
    {
        static void Main(string[] args)
        {
            List<Tree> treelist = new List<Tree>();

            string[] input = Console.ReadLine().Split(' ');
            int N = Int32.Parse(input[0]);  //나무 갯수
            int M = Int32.Parse(input[1]);  //집으로 가져갈 나무 길이

            string[] input2 = Console.ReadLine().Split(' ');
            for (int i = 0; i < N; i++)
            {
                Tree tree = new Tree(Int64.Parse(input2[i]));
                treelist.Add(tree);
            }

            Binary(treelist, N, M);
        }

        static void Binary(List<Tree> treelist, int N, int M)
        {
            long right = treelist.Max(x => x.length);
            long left = 0;

            long result = 0;

            while(left<=right)
            {
                long mid = (right + left) / 2;
                long sum = 0;    //자르고 난 나무 길이의 합
                Console.WriteLine("mid: "+mid);
                Console.WriteLine("left: "+left);
                Console.WriteLine("right: "+right);

                for(int i=0; i<N; i++)
                {
                    if(mid<treelist[i].length)
                    {
                        Console.WriteLine("mid: {0}, tree길이: {1}",mid,treelist[i].length);
                        sum += treelist[i].length - mid;
                        Console.WriteLine("sum: " + sum);

                    }
                }

                Console.WriteLine("총 sum: "+sum);
                Console.WriteLine();

                if (sum < M)
                {
                    right = mid - 1;
                }
                else if (sum >= M)
                {
                    left = mid + 1;

                    result = mid;
                    
                }
            }

            Console.WriteLine(result);

        }
    }
}