백준 6236 용돈 관리 (JAVA 자바 풀이)

백준 6236 용돈 관리 (JAVA 자바 풀이)

 

---

 

 

 

문제

현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 하였다. 현우는 통장에서 K원을 인출하며, 통장에서 뺀 돈으로 하루를 보낼 수 있으면 그대로 사용하고, 모자라게 되면 남은 금액은 통장에 집어넣고 다시 K원을 인출한다. 다만 현우는 M이라는 숫자를 좋아하기 때문에, 정확히 M번을 맞추기 위해서 남은 금액이 그날 사용할 금액보다 많더라도 남은 금액은 통장에 집어넣고 다시 K원을 인출할 수 있다. 현우는 돈을 아끼기 위해 인출 금액 K를 최소화하기로 하였다. 현우가 필요한 최소 금액 K를 계산하는 프로그램을 작성하시오.

입력

1번째 줄에는 N과 M이 공백으로 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ N)

2번째 줄부터 총 N개의 줄에는 현우가 i번째 날에 이용할 금액이 주어진다. (1 ≤ 금액 ≤ 10000)

출력

첫 번째 줄에 현우가 통장에서 인출해야 할 최소 금액 K를 출력한다.

 

 

 

---

 

 

💡 풀이 과정

 

다음과 같은 입력을 생각해보자. 

7 3 

100

400

300

100

500

101

400 

 

해당 문제의 답은 800이다. 왜 그럴까? 

 

총 인출 횟수는 3이어야 한다. 

처음 800을 인출하면 100, 400, 300을 충당한다. 이후 다시 800을 충당하면 100, 500, 101을 충당한다. 마지막 인출 시에 400을 충당한다. 

 

만약에 800원 보다 더 큰값이면 어떨까? 돈이 남을 것이므로 3번으로 맞출 수 있겠지만 그렇게 되면 최소값이 아니다. 

 

만약 800원 보다 작으면 어떨까? 799은 왜 안되는지를 살펴보자. 

 

처음 799을 인출하면 100, 400을 사용한다. 이후 두번째 인출시에 300,100을 쓴다. 그 다음 인출시에 500, 101을 사용한다. 한번 더 인출을 해야 400을 쓸 수 있으므로 총 4번 인출을 하게 된다. 

 

여기서 도출할 수 있는 개념을 생각해보면 다음과 같다.

- 최소 인출 횟수가 원하는 M 보다 크다면 k보다 큰 값을 인출해야 한다. 

- 최소 인출 쇳수가 원하는 M보다 작거나 같다면 더 적은 금액을 확인해야 한다. 

 

그렇다면 isPossible 결정 함수를 구현해보자. 

 

public static boolean isPossible(int[] plannedUsingMoney, int x, int M_WithdrawlCounts) {
   int count = 1;
   int current = x; // 현재 인출한 금액

   for (int money : plannedUsingMoney) {
      if (current < money) { // 현재 금액으로 충분하지 않으면 인출

         if(count >= M_WithdrawlCounts) { // 카운트 횟수가 중간에  M_WithdrawlCounts보다 같거나 커지면 false
            return false;
         }

         count++;
         current = x;
      }
      current -= money; // 남은 금액 업데이트
   }

   return count <= M_WithdrawlCounts;
}

 

 

이 판정 함수에 대해서 파라미터로 조사하고자 하는 인출 금액의 범위를 지정해보자. 

 

조사 범위의 가장 작은 부분은 주어진 값들 중 가장 작은 값이어야 한다. 그렇지 않으면 해당 날짜에 사용이 불가능하므로 성립이 안되기 때문이다. 

 

가장 큰 부분은 어떨까? 전체 날짜의 최대 값인 10000을 곱한 값이 될 것이다. 

 

int l = max; // 최소 인출 금액은 가장 큰 금액과 같거나 커야 함
int r = 10000 * N_Days; // 최대 인출 금액은 모든 금액의 합과 같거나 작음
int answer = r;

while (l <= r) {
   int mid = (l + r) / 2;
   if (isPossible(plannedUsingMoney, mid, M_WithdrawlCounts)) {
      answer = mid;
      r = mid - 1;
   } else {
      l = mid + 1;
   }
}

 

 

즉, 임의의 인출 금액에 대해서, N 번 이하로 출금을 했을 때 가능할 것이므로 정답 후보로 answer를 초기화 시키고 

반대고 해당 인출 금액으로 불가능 하다면 => 오른쪽으로 이동해서 탐색한다. 

 

시간 복잡도는 결정 함수에서 O(N)이고 이분 탐색이 logn이므로 O(n*logn)이 될 것이다. 

 

 

💡 코드 구현

 

import static java.lang.Integer.*;

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

public class Main {

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

      // BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
      BufferedReader bufferedReader = new BufferedReader(new FileReader("input.txt"));

      StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
      int N_Days = parseInt(stringTokenizer.nextToken());
      int M_WithdrawlCounts = parseInt(stringTokenizer.nextToken());

      int[] plannedUsingMoney = new int[N_Days];
      int min = MAX_VALUE;
      int max = MIN_VALUE;
      for (int i = 0; i < N_Days; i++) {
         stringTokenizer = new StringTokenizer(bufferedReader.readLine());
         plannedUsingMoney[i] = parseInt(stringTokenizer.nextToken());
         min = Math.min(min, plannedUsingMoney[i]);
         max = Math.max(max, plannedUsingMoney[i]);
      }


      int l = max; // 최소 인출 금액은 가장 큰 금액과 같거나 커야 함
      int r = 10000 * N_Days; // 최대 인출 금액은 모든 금액의 합과 같거나 작음
      int answer = r;

      while (l <= r) {
         int mid = (l + r) / 2;
         if (isPossible(plannedUsingMoney, mid, M_WithdrawlCounts)) {
            answer = mid;
            r = mid - 1;
         } else {
            l = mid + 1;
         }
      }
      System.out.println(answer);
   }

   public static boolean isPossible(int[] plannedUsingMoney, int x, int M_WithdrawlCounts) {
      int count = 1;
      int current = x; // 현재 인출한 금액

      for (int money : plannedUsingMoney) {
         if (current < money) { // 현재 금액으로 충분하지 않으면 인출

            if(count >= M_WithdrawlCounts) { // 카운트 횟수가 중간에  M_WithdrawlCounts보다 같거나 커지면 false
               return false;
            }

            count++;
            current = x;
         }
         current -= money; // 남은 금액 업데이트
      }

      return count <= M_WithdrawlCounts;
   }
}

 

 

---

 

참고자료: 패스트캠퍼스 핵심유형 20개로 한 번에 끝내는 알고리즘 코딩테스트 with Java