백준 No.6236 용돈 관리- JAVA

문제

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

 

 

풀이

해당 문제는 계속 생각만하다가 못 풀었다.. 그래서 결국 접근 방식은 

먼저 시작점과 끝점을 정하는데 무조건 크게 잡아야한다. 왜냐하면 일단 최대한 K를 큰 값으로 꺼내고,

M을 최소화해야한다. 그러면서 M을 찾아가는 방식으로 풀어야 정답이 나왔다

start는 주어진 값 중 가장 큰 값, 그리고 end는 해당 배열 값들을 모두 더한 값(최댓값을 줘도 가능-문제에서 준 최댓값)

그러고 나서 문제에서는 메소드를 하나만든다 해당 메소드는 mid를 파라미터로 받아 해당 mid를 계쏙 배열 하나씩 - 한다. 그런데 여기서 만약 주어진 mid가 하나씩 - 한 값이 0 미만일 경우 돈을 더 뽑아야 하므로 카운트를 계속 늘려서 반환한다. 

그러면 해당 mid일 경우 돈을 몇번 뽑아야 하는지가 나온다. 해당 횟수가 M 보다 작다면 end 값을 mid -1로 해줘야 한다. 그래야 돈을 인출하는 횟수가 증가하니까 그렇다 반대의 경우 start = mid+1;

 

import java.awt.print.PrinterGraphics;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {


    static int arr[];

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

        String[] str = br.readLine().split(" ");

        int N = Integer.parseInt(str[0]);
        int M = Integer.parseInt(str[1]);

        arr =  new int[N];


        int end = 0;
        int start = 0;
        int max = 0;
        int result = 0;
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
            end += arr[i];
            max = Math.max(max,arr[i]);

        }
        //돈을 가장 많이 쓰는 날 이상의 금액을 인출해야 한다.
        // 그렇지 않으면ㄴ 인출을 하더라도 금액이 부족하기 때문에 계속 인출을 반복한다.

        start = max;

        while (start <= end){
                int mid = (start + end)/2;
                // 지정한 횟수 이하의 횟수만큼 인출해야 할 경우,
                // 인출 금액이 더 적은 경우에 해답이 있는지 탐색해 봐야 한다.
                if(M >= getMid(mid)){
                    result = mid;
                    end = mid - 1;
                    //지정한 횟수보다 더 많이 인출해야 할 경우
                    //이눛ㄹ 금액이 더 커야한다.
                }else{
                    start = mid+1;
                }
        }

        System.out.println(result);
    }

    static int getMid(int tempMoney){
        int count = 1;
        int money = tempMoney;

        for(int num : arr){
            money -= num;// 여기서 money는 하루 쓸 돈인데 0이상이면 인출한 돈이 모자라므로 한번 더 인출

            if(money < 0){
                count++;
                money = tempMoney - num;
            }

        }
        return count;
    }
}

 

 

참고

https://velog.io/@ilil1/%EB%B0%B1%EC%A4%80-6236%EB%B2%88-%EC%9A%A9%EB%8F%88-%EA%B4%80%EB%A6%AC-java

[백준] 6236번 용돈 관리 java