[240314] 알고리즘 리부트 31일차 - 백준 6236 자바

[Part1-Chapter07-Clip09]

- 백준 6236 용돈관리

항상 고민하는 부분인데 코드를 간결하게 작성하는 것이 필요하지만 또 한 편으로는 협업을 고려해 구체적으로 작성하다보면 내 코드는 줄줄이 길어지는 경우가 많더라. 아직은 후자를 기준으로 두고 작성하지만 이러다 불필요한 자료구조나 변수 선언으로 메모리 효율이 낮아질 것 같아 고민이다.

아래 코드는 기존의 이분 탐색과 크게 다르지 않다. 다만 금액이 이번에 지출해야 하는 금액보다 적게 남았을 때는 해당 금액을 반환하고 다시 인출한다는데 총 인출할 수 있는 금액이라는 게 정해져 있지 않기 때문에 로직적으로만 생각하면 결국 그냥 잔돈이 기본 인출금액으로 리셋되면 된다.

반대로 금액이 이번에 지출해야 하는 금액보다 많이 남았을 때가 고민되는 지점인데 나는 일단은 굳이 추가 인출하지 않는 방향을 선택하고 다만 추가 인출할 수 있었던 경우를 카운트해뒀다. 이렇게 구현하면 먼저 추가 인출하지 않고도 필수적으로 인출해야 하는 횟수를 가지고 판별하고 그 수가 m 보다 작을 경우 추가 인출 가능 횟수를 반영해 m을 만들어내는 경우를 반환할 수 있기 때문이다. 

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

public class Main {
    public static int n, m, cnt;
    public static int[] spending;

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

        String nAndM = br.readLine();
        n = Integer.parseInt(nAndM.split(" ")[0]);
        m = Integer.parseInt(nAndM.split(" ")[1]);

        spending = new int[n];

        int totalSpending = 0;

        int min = 0;

        for (int i = 0; i < n; i++) {
            spending[i] = Integer.parseInt(br.readLine());
            totalSpending += spending[i];
            min = Math.min(min, spending[i]);
        }

        int l = min;
        int r = totalSpending;
        int ans = -1;

        while (l <= r) {
            int mid = (l + r) / 2;

            int tmpCnt = getWithdrawCnt(mid);
            
            if (tmpCnt == -1) {
                l = mid + 1;
            } else if (tmpCnt == m) {
                r = mid - 1;
                ans = mid;
            } else if (tmpCnt > m) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }

        System.out.println(ans);

    }

    private static int getWithdrawCnt(int mid) {
        int cnt = 1;
        int possible = 0;
        int remaining = mid;


        for (int s : spending) {
            if (mid < s) {
                return -1;
            }
            if (remaining == 0) {
                cnt++;
                remaining = mid;
            }

            if (s > remaining) { // 부족하면 남은 금액 입금하고 다시 인출
                cnt++;
                remaining = mid;
                remaining -= s;
            } else { // 원칙적으로 인출하지 않으나 인출 가능했던 횟수는 카운팅
                remaining -= s;
                possible++;
            }
        }

        if (cnt < m && cnt + possible >= m) {
            return m;
        }
        return cnt;
    }
}