[백준] 1654 랜선 자르기(C#)

문제

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

1654번: 랜선 자르기

이진 탐색이다.

코드

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 k = input[0]; // 영식이가 가진 랜선의 개수
            int n = input[1]; // 만들고 싶은 랜선의 개수

            int[] len = new int[k];
            long end = 0;
            for(int i = 0; i < k; i++)
            {
                len[i] = int.Parse(Console.ReadLine());

                if(len[i] > end)
                {
                    end = len[i];
                }
            }

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

                foreach(int l in len)
                {
                    cnt += l / mid;
                }

                if(cnt >= n)
                {
                    start = mid + 1;
                }
                else
                {
                    end = mid - 1;
                }
            }
            
            Console.Write(end);
        }
    }
}

고민

나무 자르기와 동일한 문제였다. 

 

1. 가장 긴 길이를 end로, 가장 짧은 길이를 start로(문제에서 1부터 주이지기 때문에 start를 1로 해준다)

2. for문을 돌면서 mid를 구하고 mid값으로 전선을 잘라봤을 때 내가 원하는 개수만큼 나오는지 확인한다.

3. 만약 내가 원하는 개수만큼 나오지 않는다면? 전선을 더 짧게 잘라야한다. end = mid - 1

4. 만약 내가 원하는 개수만큼 나왔다면? 어? 더 길에 잘라볼까? start = mid + 1

5. 만약 start가 end와 같아지거나 커지는 지점이 온다면 더이상 유효한 범위가 아니므로(당연함. 가장 짧은 길이가 start라고 했고 긴 길이가 end라고 했는데 start가 end랑 같거나 커지면 계산이 허용 안되어야함) 조건문을 탈출하고 콘솔에 end 혹은 start - 1을 출력해준다.

 

왜 end 혹은 start-1이지?

start와 end는 우리가 검색하고자 하는 범위의 양 끝을 나타낸다. 하한값 = start, 상한값 = end

우리가 찾는 것은 n개 이상의 랜선을 만들 수 있는 최대 랜선의 길이 이므로 start가 end를 넘어가는 순간 'end'가 가능한 답의 최대값임을 알게 되는 것이다... 

 

그래서 우리는 end를 출력하거나 start가 end를 넘어가기 이전인 start-1을 출력해야 하는 것이다.

 

 

 

이 문제를 풀기위해 많은 시련과 역경이 있었다.

 

1. int 타입의 최대가 들어오기 때문에 long타입으로 변경

2. start가 0이 될 경우 0을 나누는 불상사가 생기기 때문에 start를 1로 변경(문제에서도 제일 작은게 1이라고 되어있음)