[BOJ][C#] 6236 용돈 관리

📕 문제

📌 링크

📗 접근 방식

1. N과 M을 입력받는다.
2. 일일 금액 리스트를 입력받는다.
3. 최대 출금 횟수와 일일 금액 리스트를 매개변수로 이분 탐색 함수로 진입한다.
   • 이분탐색의 범위는 0 ~ int.MaxValue (이유는 오답노트에)
   • list[i]는 i번째 날 사용하는 금액이다.
   • 일일 금액이 mid(지정 금액)보다 크다면
     • 절대 인출을 할 수 없기 때문에 can을 False로 변경 후 탐색을 종료한다.
   • 일일 금액보다 소지 금액이 적다면
     • 소지 금액을 입금하고 mid만큼 인출한다.
   • 소지 금액에서 일일 금액을 차감한다.
   • can이 True라면
     • 출금 횟수가 최대 출금 횟수보다 작거나 같으면 end를 옮긴다.
     • 출금 횟수가 최대 출금 횟수보다 크면 start를 옮긴다.
   • can이 False라면
     • 더 많은 금액을 인출해야하기 때문에 start을 옮긴다.
4. 탐색이 종료되었다면 start를 return하여 출력한다.

📘 코드

namespace BOJ_6236
{
    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 = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
            int N = inputs[0];
            int M = inputs[1];

            List<int> payTodayList = new List<int>();

            for (int i = 0; i < N; i++)
            {
                int pay = int.Parse(sr.ReadLine());
                
                payTodayList.Add(pay);
            }
            
            sw.Write(BinarySearch(M, payTodayList));
            
            sr.Close(); sw.Flush(); sw.Close();
        }

        static int BinarySearch(int maxCount, List<int> list)
        {
            int start = 0;
            int end = int.MaxValue;

            while (start <= end)
            {
                int mid = (start + end) >> 1;
                
                int leftMoney = 0;
                int count = 0;
                bool can = true;
                for (int j = 0; j < list.Count; j++)
                {
                    // list[j] : j날 사용하는 금액 (일일 금액)
                    
                    // 일일 금액이 mid보다 크다면
                    if (list[j] > mid)
                    {
                        // 절대 인출할 수 없는 금액이기 때문에
                        // start값을 증가시켜야함
                        can = false;
                        break;
                    }
                    
                    // 일일금액보다 소지량이 적다면
                    if (leftMoney < list[j])
                    {
                        // 소지량은 입금 mid만큼 출금
                        leftMoney = mid;
                        count++;
                    }

                    leftMoney -= list[j];
                }

                if (can == true)
                {
                    // 출금횟수가 M보다 작거나 같으면
                    if (count <= maxCount)
                    {
                        end = mid - 1;
                    }
                    // 출금횟수가 M보다 크면
                    else
                    {
                        start = mid + 1;
                    }
                }
                else
                {
                    // 출금횟수가 M보다 작은 경우
                    
                    start = mid + 1;
                }
            }

            return start;
        }
    }
}

📙 오답노트

start와 end의 범위가 틀렸다. 리스트의 최소부터 최대까지만 탐색하면 될 줄 알았지만
100,000일 동안 10,000원을 쓸거고 단 한번인출을 한다면
100,000 * 10,000을 인출해야 되기때문에 리스트의 최소 최대를 탐색 범위로 지정하면 안되었다.

📒 알고리즘 분류

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