[JAVA]BOJ 6236, 용돈 관리

이진탐색을 활용한 세 번째 문제이다. 연달아 푸니 이진탐색 문제에서 중요한게 뭔지 느껴진다.. 제일 중요한건 이진탐색할 범위이다. 범위를 잘못 정하면 아무리 이진탐색을 해도 정답을 맞출 수 없다.

 

질문게시판을 보니, 문제가 이해 안된다는 글이 매우 많았다.. 예전에는 더 복잡하게 문제가 적혀있었나? 아무튼.. 지금 돈이 있으면 쓰고, 없으면 출금한다. 근데 그냥 출금하면 안되고 지금 있는 돈 다시 통장에 다 넣어서 0원 만들고 출금해야한다. 문제에서 준 예제 7 5 / 100 400 300 100 500 101 400 으로 입출금내역을 정리하면 아래와 같다. *는 출금, -는 사용한 돈, = 는 돈 쓰고 남은 현재돈

*+500 // 첫 출금
-100 // 첫째날 100원 씀
=400 // 400원 남음
-400 // 둘째날 400원 씀
=0 // 0원 남음
*+500 // 셋째날 300원 쓰려는데 돈 없으니까 출금
-300 // 셋째날 300원 씀
=200 // 200원 남음
-100 // 넷째날 100원 씀
=100 // 100원 남음
-100 *+500 // 다섯째날 500원 쓰려는데 부족하니까 현재있는 돈 입금하고 출금 -> 현재 500원있음
-500 // 다섯째날 500원 씀
=0 // 0원 남음
*+500 // 여섯째날 101원 쓰려고 출금
-101 // 여섯째날 101원씀
=399 // 399원 남음
-399 +*500 // 일곱째날 400원 쓰려는데 부족하니까 현재있는 돈 입금하고 출금 -> 현재 500원있음
-400 // 일곱째날 400원 씀
=100 // 100원 남음

 

*는 5번 = 5번 출금함,

이런식으로 입출금이 이뤄지고 횟수를 센다고 생각하면 된다.

 

---

이번에는 반복문을 이용해 이진탐색을 했다. 재귀에 비해 훨씬 코드가 쉽고, 이해하기도 좋다.

3개의 함수로 구성되고 각각 main문 , 이진탐색, 인출횟수구하기 의 기능을 한다.

 

쉬운 인출 횟수 구하기부터 설명..

1. 인출 횟수 구하기

public static int countWithdraw(int[] spending, int money, int M){
    int wallet = money, i = 0, cnt = 1; // 1번 인출함

    while(i < spending.length){
        if(wallet >= spending[i])
            wallet -= spending[i++];
        else{
            wallet = money; // 돈을 빼고 다시 저장함
            cnt++;
            wallet -= spending[i++];
        }
    }
    return cnt;
}

 

특정한 money가 주어졌을때 총 몇 번 인출하는지 구한다. 특이한 부분은 돈이 부족해서 다시 인출할때, 문제에서 지갑에 남은 돈을 다 통장에 넣고 money만큼만 인출하라고 했다. 예를 들면 money = 10, 현재 돈 = 3, 쓸 돈 = 7 인 경우, 현재 돈 = 3 에서 -3을 하고, +10을 해 현재 돈 = 10을 만들어야 한다. 현실에서라면 귀찮게 입출금해야겠지만 코드상에서는 그냥.. 현재돈 = money 로 만들어주면 된다. 그리고 이는 출금을 뜻하니 cnt를 증가시킨다. 

 

2. 이진 탐색

이진 탐색의 범위는 어떻게 될까? 돈이 부족할때 그냥 출금하는게 아니라 0원으로 만들고 출금을 하므로, 최소 출금 금액은 1일 지출의 max값이 된다. 문제 예제( 7 5 / 100 400 300 100 500 101 400 )에서 500원이 최소 출금 금액이다. 그러면 최대 출금 금액은..? 사실 상관없다..10,000원으로 해도 되긴하다. 그치만 효율성을 생각하면 굳이 그럴 필요없다.

만약 원하는 출금 횟수가 1번일때 최소 출금액은 얼마일까? 모든 일일 지출액의 합이 될것이다. 당연히.. 5일간 100원을 쓸거면 첫째날에 500원을 미리 출금하면 되니까. 물론 10,000원을 꺼내도 되지만 이건 최소금액이 아니다. 그래서 이진탐색의 범위는

일일 최대 지출 <= 답 <= 일일 지출들의 합

이 된다.

 

이진탐색 범위를 구했으니 진짜 해보자. 앞에서 한 랜선 자르기(1654)와 유사하다.

public static int binarySearchLoop(int[] spending, int low, int high, int M){
    int mid, result, ans = 0;

    while(low <= high){
        mid = (low + high) / 2;
        result = countWithdraw(spending, mid, M);

        if(result <= M){
            ans = mid;
            high = mid - 1;
        }
        else{
            low = mid + 1;
        }
    }

loop를 써서 랜선 자르기 문제보다 훨씬 더 간결하고 이해하기 쉽다. 출금횟수를 구해서(result) M과 비교한다. 보통 이진탐색은 == M , < M, > M 이 세 경우를 보는데, 이 문제는 <= M과 > M으로 나뉜다. M이 되는 최솟값을 구하기 위해서이다.

새로운 간단한 예시를 들어보자.

3 3
100
100
100

low~high, mid(출금횟수)
100~300, 150(3) -> 100~149, 124(3) -> 100~123, 111(3) -> 100~110, 105(3) -> 100~104, 102(3) -> 100~101, 100(3) -> 100~100, 100(3) -> 100~99 끝

ans = 100

조건을 == M으로 주면 150(3)에서 이미 끝나버린다. 최솟값을 구하지 못한다.. 100 ~ 149에 최솟값이 있고 이진탐색을 더 해서 찾아야한다. 그래서 <= M 으로 조건을 주어야 최솟값을 구할 수 있다.

---

아래는 전체 코드이다.

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

public class BOJ6236 {
    public static int countWithdraw(int[] spending, int money, int M){
        int wallet = money, i = 0, cnt = 1; // 1번 인출함

        while(i < spending.length){
            if(wallet >= spending[i])
                wallet -= spending[i++];
            else{
                wallet = money; // 돈을 빼고 다시 저장함
                cnt++;
                wallet -= spending[i++];
            }
        }
        return cnt;
    }

    public static int binarySearchLoop(int[] spending, int low, int high, int M){
        int mid, result, ans = 0;

        while(low <= high){
            mid = (low + high) / 2;
            result = countWithdraw(spending, mid, M);

            if(result <= M){
                ans = mid;
                high = mid - 1;
            }
            else{
                low = mid + 1;
            }
        }
        return ans;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N, M, i, totalMoney = 0, max = 0;
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        int[] spending = new int[N];

        for(i=0;i<N;i++) {
            spending[i] = Integer.parseInt(br.readLine());
            totalMoney += spending[i];

            if(spending[i] > max)
                max = spending[i];
        }

        System.out.println(binarySearchLoop(spending, max, totalMoney, M));
    }


}