[백준-6236] 용돈 관리 .java

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

문제 이해가 어려웠는데 이해만 하면 쉽다

• 무조건 첫날엔 돈이 없으므로 인출해야함 (k만큼) => 이를 며칠동안 나눠서 씀
• 하루마다 정해진 돈을 씀 -> 이미 지갑에 있는 돈으로 지불 할 수 없음 
• 남은 돈은 다시 통장에 넣고(더이상 계산하지 않음) k만큼 인출
• 인출의 최소 금액을 구하려면 인출 횟수가 많으면 안 됨 -> 인출 횟수가 m번 이하여야함
• 최소 인출횟수 ≤ M이라면 k는 답이 될 수 있으며 더 적은 금액에 대해 확인
• 최소 인출횟수 > M이라면 k보다 큰 금액을 인출
• 단, 하루에 쓸 돈이 인출할 수 있는 금액보다 크면 사용 불가능
• 최소금액 k를 구하는게 포인트 -> r이 mid-1이여야함

 

처음에 남은돈을 사용하면서  k만큼 인출하는 줄 알았는데, 통장에 집어놓고의 의미가 더이상 계산하지 않는 의미였다

또한 r의 최댓값은 모든 날마다 최대금액을 사용할때 -> 10000원 * n일이 된다

 

 

import java.util.Scanner;


public class Solution {
	//인출 금액으로 m번 이하 인출로 모든 날 가능한지 
	public static boolean isPossible(int[] money, long cut, int m) {
		long cur = cut;
		int count =1;
		for(int i : money) {
			//하루 필요 금액이 cut보다 크면 불가능
			if(i>cut) return false;
			//현재 가진 돈으로 해당 날의 지출을 못하는 경우 ->인출해야 함
			if(i>cur) {
				cur = cut;//인출
				count++;//인출 횟수 증가
			}
			cur -= i;//금액 사용
			
		}

		return count <=m;
	}


    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
    	
    	int n = sc.nextInt();
    	int m = sc.nextInt();
    	int[] money = new int[n];

    	for(int i =0; i<n; i++) {
    		money[i] = sc.nextInt();

    	}
    	
    	//최대 인출 금액 (모든 날이 최대 10000원일 경우)
    	long l = 1, r= 10000*n, answer=0;
    	
    	while(l<=r) {
    		
    		long mid = (l+r) /2;
    		
    		if(isPossible(money,mid,m)) {//더 작은 값 되는지
    			answer = mid;
    			r = mid-1;
    		}else l = mid+1;
    		
    	}

    	
   		System.out.print(answer);
    	
    
     }
    
}

 

 

문해력 싸움.....