[BOJ][C#] 2512 예산

📕 문제

📌 링크

📗 접근 방식

1. 입력으로 주어진 지방 예산을 배열에 저장하고 정렬
2. 이분 탐색을 수행
   이분 탐색을 통해 나온 값들로 지방 예산을 계산(GetTotalCost())하고 m과 비교하여 start값을 옮길지 end값을 옮길지 결정한다.

📘 코드

namespace BOJ_2512
{ 
    class Program
    {
        private static int n, m;
        private static int[] provinces;
        
        static void Main()
        {
            n = int.Parse(Console.ReadLine());
            provinces = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            m = int.Parse(Console.ReadLine());

            Array.Sort(provinces);
            
            int start = 1;
            int end = provinces[n-1];

            while (start <= end)
            {
                int mid = (start + end) / 2;
                int cost = GetTotalCost(mid);

                if (cost <= m)
                {
                    start = mid + 1;
                }
                else
                {
                    end = mid - 1;
                }
            }

            Console.WriteLine(end);
        }

        static int GetTotalCost(int num)
        {
            int ret = 0;
            
            for (int i = 0; i < n; i++)
            {
                if (provinces[i] <= num)
                {
                    ret += provinces[i];
                }
                else
                {
                    ret += num;
                }
            }

            return ret;
        }
    }
}

📙 오답노트

시간초과 - GetTotalCost를 이분탐색을 돌며 진행하는데 while문 돌면서 한번만 진행하면 되었지만 if 조건문에 GetTotalCost를 작성하였다. 또한, if - else로 작성하면 되는 문제를 굳이 if - else if - else문으로 구분하여 시간복잡도를 증가시켰다.

📒 알고리즘 분류

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