BOJ 6236 - 용돈 관리

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

6236번: 용돈 관리

 

 

• N일 동안 사용 (1 ≤ N ≤ 100,000)
• 통장에서 M번만 출금 (1 ≤ M ≤ N)
• i번째 날에 이용할 금액 (1 ≤ 금액 ≤ 10000)
• 현우가 통장에서 인출할 최소 금액 K 값은?

 

아이디어

' 최소 ' 키워드가 나왔으므로 이분 탐색으로 먼저 접근해보았다.

 

원래 문제

N일동안 통장에서 M번만 출금할 때 한번에 인출할 최소 금액 K 값은?

 

최소 금액 K를 매개 변수로 설정하고 문제를 뒤집어서 Yes or No 결정 문제로 바꾼다.

 

뒤집어서 만든 Yes or No 문제

한번에 K 금액만큼 인출할 때 N일동안 M번 출금해서 사용 가능한가? Yes or No?

 

Yes or No 문제 풀이

한번에 K만큼 인출할 수 있으므로 for문으로 처음부터 더해서 인출 횟수를 구한다. 그 후 인출 횟수와 M을 비교한다.

static boolean YesOrNo(int K) {
    int sum = 0;
    int cnt = 1;

    for (int i = 1; i <= N; i++) {
        // 금액이 인출한 K보다 클 경우
        if(sum + amount[i] > K) {
            // 한번 더 인출
            cnt++;
            // 새로 인출했으니 sum 갱신
            sum = amount[i];

        // K 안에서 해결 가능한 경우
        } else {
            sum += amount[i];
        }
    }

    return cnt <= M;
}

이분탐색

이분탐색의 범위는 N의 최댓값이 100000이고, 하루 최대 이용 금액이 10000이므로 최대 10억이다. 

또한 N일동안 필요한 금액의 최댓값을 최소로 잡는다.

범위 : ( N일 동안 필요한 금액의 최댓값 ~ 10억 )

 

K값의 최소를 구해야 하므로 처음으로 Yes가 나온 지점을 구한다.

 

시간 복잡도

• Yes or No 문제 풀 때 O(N)
• 이분 탐색의 범위가 약 10억이므로 O(log 10억)
• 총 O(N log 10억) 이므로 시간안에 풀이가 가능하다.

 

구현

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

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N, M, sum;
    static int[] amount;

    static void init() 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());

        amount = new int[N + 1];
        sum = 0;
        for (int i = 1; i <= N; i++) {
            amount[i] = Integer.parseInt(br.readLine());
            sum += amount[i];
        }

    }

    static void pro() throws IOException {
        // 이분 탐색
        int L = amount[1];
        for (int i = 1; i <= N; i++) {
            L = Math.max(amount[i], L);
        }

        int R = 1000000000;
        int ans = 0;

        while (L <= R) {
            int mid = (L + R) / 2;

            if (YesOrNo(mid)) {
                ans = mid;
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }

        bw.write(ans+" ");
    }

    static boolean YesOrNo(int K) {
        int sum = 0;
        int cnt = 1;

        for (int i = 1; i <= N; i++) {
            // 금액이 인출한 K보다 클 경우
            if(sum + amount[i] > K) {
                // 한번 더 인출
                cnt++;
                // 새로 인출했으니 sum 갱신
                sum = amount[i];

            // K 안에서 해결 가능한 경우
            } else {
                sum += amount[i];
            }
        }

        return cnt <= M;
    }

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

        pro();

        bw.close();
    }

}