백준 6236번) 용돈 관리 (JAVA)

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

6236번: 용돈 관리

 

#문제

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

 

#알고리즘

이분탐색

매개 변수 탐색

 

#난이도

Silver 2

 

#풀이방법

계속해서 이분탐색 문제를 풀이 하겠다.

이분탐색의 핵심은 탐색의 start와 end를 찾아 조건에 맞으면 문제에서 제시하는 답을 대입하여 최소 or 최대를 구하는 것이다.

 

예제를 들어 설명하면 예제에서 각 날짜마다 소비해야하는 금액은 100,400,300,100,500,101,400인데 날짜마다 돈을 쓰기 위해서는 최소 금액은 각 날 소비해야하는 금액보다는 같거나 많아야 한다. 같거나 많아야 하는 금액 중 최소 금액은 소비해야하는 금액 중 제일 큰 금액인 500이고, 최대금액은 돈 인출을 한번만 할 수 있는 금액 즉 소비해야하는 모든 날들의 금액을 더하는 값이 최대 금액이다.

 

요약하면

int start = 500;

int end = 100+400+300+100+500+101+400이다.

 

        int start = 0;
        int end = 0;
        
        for(int i=0; i<spend.length; i++) {
            
            spend[i] = sc.nextInt();
            
            if(start < spend[i])
                start = spend[i];
            
            end += spend[i];
            
        }

 

 

    while(start <= end) {            
            int mid = (start + end)/2;
            //인출해야 할 최소 금액
            
            int wd = 1;//최소 한번의 인출 필요
            int money = mid;
            
            for(int i=0; i<spend.length; i++) {
                
                if(money >= spend[i]) {
                    money -= spend[i];
                }
                else {
                    money = mid;
                    money -= spend[i];
                    wd++;
                }//돈이 부족하므로 인출
                
            }
            
            if(wd > M) {
                start = mid + 1;
            }
            else {
                an = mid;
                end = mid - 1;
            }
            
            
            
        }

 

최소 한번의 인출이 필요하고, 각 소비해야하는 날을 for문으로 비교하여 돈이 부족할 경우 money = mid로 넣고

인출한 횟수를 늘려주는 횟수로 조건에 맞는지 탐색한다.

 

인출횟수가 너무 많은 경우 인출해야 하는 금액을 늘려주고 

인출횟수가 적은 경우 조건에는 맞으므로, 그 중 an = mid로 an을 초기화 시켜준다.

 

#전체 코드

 

import java.util.*;
//1t
 
public class Main {
 
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        int N = sc.nextInt();
        int M = sc.nextInt();
        
        int[] spend = new int[N];
        
        int start = 0;
        int end = 0;
        
        for(int i=0; i<spend.length; i++) {
            
            spend[i] = sc.nextInt();
            
            if(start < spend[i])
                start = spend[i];
            
            end += spend[i];
            
        }
        
        int an = end;
        
        while(start <= end) {
            
            int mid = (start + end)/2;
            //인출해야 할 최소 금액
            
            int wd = 1;//최소 한번의 인출 필요
            int money = mid;
            
            for(int i=0; i<spend.length; i++) {
                
                if(money >= spend[i]) {
                    money -= spend[i];
                }
                else {
                    money = mid;
                    money -= spend[i];
                    wd++;
                }//돈이 부족하므로 인출
                
            }
            
            if(wd > M) {
                start = mid + 1;
            }
            else {
                an = mid;
                end = mid - 1;
            }
            
            
            
        }
        
        
        
        System.out.println(an);
        
    
        
    }
 
}