[JAVA][BOJ]6236. 용돈 관리

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

 

---

풀이 과정

문제 이해가 살짝 어려웠던 문제..

원래 술술 읽으면 이해가 되는데 얘는 이해가 안돼서 종이에 쓰면서 해석했다..

내가 문해력이 안좋은건지 글이 이상한건지..?

중요한 부분만 뽑아보면

 

1. N일 동안 사용할 금액이 주루룩 있음

2. 정확히 M번만 돈을 뺄 것임! (돈 아끼려고 하는거라서 M보다 적어도 됨)

3. 한번 인출할때 무조건 k원을 뺄것임. 이는 고정 값이고 수중에 있는 돈이 하루를 보내기에 부족하면

    원래있던 돈 전부 통장에 집어넣고, k원 인출

이 정도 인 것 같은데

 

아마 다들 2번에서 뭐라굽쇼..? 하지 않을까...

정확히 M번이라고 했는데 사실 이 부분은 문제 풀다보면 신경쓰지 않아도 됨

왜냐하면 우리는 금액(k)을 최소화 하는 것을 목표로 할 것이고, 그러면 돈을 인출하는 횟수는 최대가 될 수 밖에 없기 때문.

난 무조건 M을 만들어야된다는 생각에 이리저리 헤맸는데 생각해보니 그게 아니었다...

 

그래서 이제 문제 이해는 끝났고 문제를 어떻게 풀지 생각을 해보면

1. 일단 N크기 배열 만들어서 하루하루 필요한 돈을 저장해놓고,

2. 이제 k의 값을 찾아야 된다는 것인데, k가 나올 수 있는 구간을 정해놓고 이분탐색으로 찾으면 될 것 같다.

최소값이야 뭐 0으로 놓고 시작해도 되니깐 최댓값을 구해야하는데

인출할 수 있는 횟수(M)가 1일수도 있으니깐 모든 날써야하는 돈을 한번만 뽑은 N * 10000 이 max일 것이다.

3. 임시 k금액을 정했다면 배열을 쭉 돌면서 해당 가격으로 M만큼 뽑아서 먹고 살 수 있는지를 확인한다.

     - 이때 k값이 arr[i]보다 작으면 못먹고 산다(그냥 최솟값을 arr 최댓값으로 해놓고 시작해도 될듯?)

     - 그 다음 현재 갖고 있는 돈이 모자라면 원래 있던 돈을 집어넣고 k원을 인출한다음 cnt 올려주고,

     - 아니면 그냥 현재 있는 돈에서 빼기만 하면 된다.

     - cnt가 중간에 M보다 늘어나면 실패

     - 모든 반복문을 돌고 문제가 없어야 성공

 

채점 결과는 성공~

 

---

풀이 코드

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

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[] arr = new int[N];
        int end = N * 10000;
        int start = 0;
        int answer = 0;

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

        while (start <= end) {
            int mid = (start + end) / 2;

            if (isPossible(arr, mid, M)) {
                answer = mid;
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }

        System.out.println(answer);
    }

    private static boolean isPossible(int[] arr, int mid, int M) {
        int cnt = 1;
        int cur = mid;
        for (int i = 0; i < arr.length; i++) {
            if (mid < arr[i]) {
                return false;
            }

            if (cur < arr[i]) {
                cnt++;
                cur = mid - arr[i];
            } else if (cur >= arr[i]) {
                cur -= arr[i];
            }

            if (cnt > M) {
                return false;
            }
        }
        return true;
    }

}