백준 6236 용돈 관리

문제

현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 하였다. 현우는 통장에서 K원을 인출하며, 통장에서 뺀 돈으로 하루를 보낼 수 있으면 그대로 사용하고, 모자라게 되면 남은 금액은 통장에 집어넣고 다시 K원을 인출한다. 다만 현우는 M이라는 숫자를 좋아하기 때문에, 정확히 M번을 맞추기 위해서 남은 금액이 그날 사용할 금액보다 많더라도 남은 금액은 통장에 집어넣고 다시 K원을 인출할 수 있다. 현우는 돈을 아끼기 위해 인출 금액 K를 최소화하기로 하였다. 현우가 필요한 최소 금액 K를 계산하는 프로그램을 작성하시오.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

        String s=br.readLine();
        StringTokenizer st=new StringTokenizer(s);
        int n=Integer.parseInt(st.nextToken()); //사용할 일 수
        int m=Integer.parseInt(st.nextToken()); //통장에서 뺄 횟수
        int[] goal=new int[n];
        for(int i=0; i<goal.length; i++)
            goal[i]=Integer.parseInt(br.readLine()); //일별로 사용할 금액

        int start=0;
        int end=0;
        for(int i:goal){
            if(i>start)
                start=i;
            end+=i;
        }

        int balance;
        while(true){
            int k=(start+end)/2;
            int count=m;
            balance=0;
            for(int i=0; i< goal.length; i++){
                if(count==(goal.length-i)){
                    balance=k;
                    count--;
                }

                if(goal[i]<=balance)
                    balance-=goal[i];
                else{
                    balance=k-goal[i];
                    count--;
                }
            }

            if(count==0)
                end=k;
            else
                start=k+1;

            if(end==start)
                break;
        }
        System.out.println(start);
    }
}

---

해결 과정

1. 인출할 금액(K)의 범위 중 최솟값을 구하는 것이기 때문에 Binary Search로 풀기 위해서 start, end의 범위를 정해봤다. 우선 start는 최대 인출 금액에서 그 날의 생활을 해야 하기 때문에 모든 날의 사용 금액 중 가장 높은 금액이 되어야 한다. 그 후 end의 경우 최대 인출 가능 횟수(M)가 1일 수도 있기 때문에 모든 날의 사용 금액의 합계로 잡아줬다.
   이렇게 범위를 지정해준 뒤에 반복문으로 Binary Search를 구현했다.

   참고로 N일 동안의 출금 횟수==M이 되어야 하기 때문에 남은 일수==남은 출금 횟수 라면 잔액이 충분해도 다시 출금 해줬다.

2. 😁