[BOJ][C#] 13702 이상한 술집

📕 문제

📌 링크

📗 접근 방식

• 주어진 n과 k가 같다면 주어진 리스트의 최솟값을 출력
• 주어진 리스트의 최댓값을 기준으로 이분 탐색을 진행하며, 나누어 떨어지는 수의 개수를 계산
  • 계산한 개수가 목표값 k보다 크거나 같으면 이분 탐색의 범위를 더 큰 값으로 이동(start = mid + 1)
  • 그렇지 않으면(작으면) 범위를 더 작은 값으로 이동 (end = mid -1)
• 이분 탐색이 끝났다면 end를 출력

📘 코드

namespace BOJ_13702
{
    class Program
    {
        static void Main()
        {
            using StreamReader sr = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
            using StreamWriter sw = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));

            int[] inputs = sr.ReadLine().Split().Select(int.Parse).ToArray();
            int n = inputs[0];
            int k = inputs[1];

            List<int> list = new List<int>();
            for (int i = 0; i < n; i++)
            {
                list.Add(int.Parse(sr.ReadLine()));
            }

            if (n == k)
            {
                sw.Write(list.Min());
            }
            else
            {
                int start = 0;
                int end = list.Max();

                while (start <= end)
                {
                    int mid = (start + end) >> 1;

                    int sum = 0;
                    for (int i = 0; i < n; i++)
                    {
                        int temp = list[i] / mid;
                        sum += temp;
                    }

                    if (sum >= k)
                    {
                        start = mid + 1;
                    }
                    else
                    {
                        end = mid - 1;
                    }
                }
                
                sw.Write(end);
            }
            
            sw.Flush(); sw.Close(); sr.Close();
        }
    }
}

📙 오답노트

📒 알고리즘 분류

• 이분 탐색
• 매개 변수 탐색