[BOJ 6236] 용돈 관리 (Java, 매개변수 탐색)

 

 

 

---

문제 링크

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

6236번: 용돈 관리

---

풀이

- 이진탐색(매개변수 탐색) 문제 

- 시간복잡도 O(NlogN)

- 은행 인출(mid) 하고 cnt = 1 한 초기 상태에서 일별 사용금액을 차감하면서 부족할 경우 추가 은행 인출(cnt += 1) 

- (100, 400), (300,100), (500), (101), (400) 형태가 

 

최대값

만약 N일이 10만이고, 각 금액이 1만이면 최대 10^9이 되야 1번(M)번에 처리가 가능 => Integer 연산 가능

 

이진탐색 범위

범위(L, R) 지정시 L 은 주어진 일자별 금액 중 최대값 선택하고, R은 전체 합으로 지정

- L :  10만(N)일 동안 10만(M)번 뽑는게 가능할 때, 10,000원씩 뽑을 수 있다면 최소 얼마를 지정해야 하는가?

- R : 만약 인출할 금액이 최대 10^9원이고, 은행에서 1번(M)만 뽑을 수 있을 때 어떻게 될 것인가?

 

기록
매개변수 탐색은 L, R 범위 지정, 데이터 타입, 조건 성립시 부등호에 주의 해야 하는 구나
최소 값을 찾는 경우 조건 성립시 R을 줄이고 
최대 값을 찾는 경우 조건 성립시 L을 증가시키는 형태를 보이는 구나

---

제출 코드

import java.util.*;
import java.io.*;

public class Main {

    static int N, M, MIN, MAX;

    static int[] A;

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        A = new int[N];
        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            A[i] = Integer.parseInt(st.nextToken());

            MIN = Math.max(MIN, A[i]);
            MAX += A[i];
        }
    }

    static boolean isValid(int money) {
        int cnt = 1;
        int wallet = money;
        for(int a : A) {
            if(wallet - a < 0) {
                cnt += 1;
                wallet = money;
            }

            wallet -= a;
        }

        return cnt <= M; // money가 최대의 경우를 생각 cnt = 1 이 되므로 범위를 좁혀야 함 
    }

    static void pro() {
        int L = MIN, R = MAX, ans = 0;
        while(L <= R) {
            int mid = (L + R) / 2;
            if(isValid(mid)) { // 조건 성립시 최소 금액을 찾기 위해 R을 줄임
                R = mid - 1;
                ans = mid;
            } else {
                L = mid + 1;
            }
        }

        System.out.println(ans);
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
}