[백준] 6236 용돈 관리 - Java

 

 

문제 출저 

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

6236번: 용돈 관리

 

 

문제 풀이

n일 동안 하루에 써야할 금액과 인출할 횟수 m이 주어집니다.

인출은 현재 가지고 있는 돈이 하루동안 써야할 금액보다 작을 때 이루어 집니다.

인출을 할 때, 기존에 가지고 있는 돈은 모두 통장에 넣습니다. (즉 초기화 된다는 얘기)

이 때, 한 번에 인출 횟수 m번을 만족하는 최저 금액을 구하는게 문제의 요구 사항 입니다. 

 

(제 기준, 문제가 모호하게 적혀있어 이해하는데 시간이 걸렸습니다)

 

이분 탐색으로 문제를 풀었습니다.

 

시작값은 주어진 하루 동안 써야할 금액 중 가장 큰 값입니다.

마지막 값은 10,000 * 100,000 입니다.

이 값은 주어진 일 수 * 하루 동안 써야할 금액의 최대치 입니다.

m이 1일 때, 즉 한 번 밖에 인출할 수 없을 때 10000일이 주어지고 그 10,000일 동안 모든 날이 100,000을 써야할 때가 가장 큰 값이 되기 때문입니다.

 

이 후 하면서 인출한 횟수를 저장한 count를 만들어 m과 count를 비교하면서 이분 탐색을 진행해 답을 구했습니다.

 

 

 

소스 코드

package baekjoon.backjoon9.day19;

/*
용돈 관리
https://www.acmicpc.net/problem/6236
 */

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

public class B6236 {

    static int n,m;
    static int[] board;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        board = new int[n];
        int largeNumber = 0;
        for(int i = 0; i < n; i++) {
            board[i] = Integer.parseInt(br.readLine());
            largeNumber = Math.max(largeNumber, board[i]);
        }

        int s = largeNumber;

        // N의 최댓값, M의 최댓값의 곱
        // e의 가장 큰 값은 M이 1일 때 N의 최대 일수인 10000일을 한 번에 인출해서 버틸 금액이어야 한다.
        // 즉 10_000 * 100_000 이어야 한다.
        // 맨 처음 Integer.MAX_VALUE 해서 42%에서 틀렸다.
        int e = 10_000 * 100_000;



        int answer = 0;

        while(s <= e) {
            int mid = (s+e)/2;

            int count = 1;
            int money = mid;

            for(int i = 0; i < n; i++) {
                money -= board[i];

                if(money < 0) {
                    money = mid - board[i];
                    count++;
                }
            }

            if(count > m) {
                s = mid + 1;
            }
            else {
                e = mid - 1;
                answer = mid;
            }
        }

        System.out.println(answer);




    }

}