[BOJ] 6236 용돈 관리 - JAVA

1. 문제

6236번: 용돈 관리

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

---

2. 풀이

입력

1.  min은 K원의 최솟값이다. 하루에 인출할 금액보다 K가 작으면 아무리 인출해도 그 날 사용할 금액을 충족할 수 없기 때문에 money배열의 최댓값을 K의 최솟값으로 삼는다.

2.  max는 K원의 최댓값이다. 인출 한 번한 금액으로 모든 날을 사용할 수 있도록 설정한다. 따라서 max에 money배열의 모든 요소를 더한 값에 +1한 것을 저장한다. (1을 더한 것은 보험용이다)

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(in.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());

int[] money = new int[N];
int min = 1, max = 1;

for(int i=0;i<N;i++) {
   money[i] = Integer.parseInt(in.readLine());
   min = Math.max(min,money[i]);
   max += money[i];
}

 

탐색 및 출력

1.  매개변수 이분탐색을 진행한다. mid값을 max,min의 중간값으로 놓고, min<=max인 경우에만 탐색한다.

2.  반복마다 sum과 count를 초기화한다.

3.  sum에 money[i]를 더한다. 만약 더한 값이 mid를 초과한다면 현대의 money[i]만 sum에 저장하고 count++한다. count를 1로 초기화하는 이유도 여기에 있다. 인출 한 번에 사용할 수 있는 연속된 날짜들의 집합을 한 구간이라고 할 때, 한 번도 mid를 넘지 않고 돈을 사용할 수 있다면 모든 날이 한 구간에 속하게 된다. sum>mid인 경우 한 구간이 둘로 쪼개진다고 생각하면 된다. 

4.  money를 전부 탐색했다면, count의 값을 M과 비교한다. M보다 더 크다면 한 번에 인출하는 양을 늘려야하므로 min에 mid+1을 저장한다. M보다 작거나 같다면 한 번에 인출하는 양을 줄여도 된다. max에 mid-1을 저장한다.

int mid, count, sum;
while(min<=max){
   mid = (min+max)/2;

   sum = 0;
   count = 1;

   for(int i=0;i<N;i++){
      sum += money[i];
      if(sum>mid) {
         sum = money[i];
         count++;
      }
   }
   if(count>M) min = mid+1;
   else max = mid-1;
}

System.out.println(min);

 

전체 코드

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

public class BOJ_6236_용돈관리 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(in.readLine());
      int N = Integer.parseInt(st.nextToken());
      int M = Integer.parseInt(st.nextToken());

      int[] money = new int[N];
      int min = 1, max = 1;

      for(int i=0;i<N;i++) {
         money[i] = Integer.parseInt(in.readLine());
         min = Math.max(min,money[i]);
         max += money[i];
      }

      int mid, count, sum;
      while(min<=max){
         mid = (min+max)/2;

         sum = 0;
         count = 1;

         for(int i=0;i<N;i++){
            sum += money[i];
            if(sum>mid) {
               sum = money[i];
               count++;
            }
         }
         if(count>M) min = mid+1;
         else max = mid-1;
      }

      System.out.println(min);
   }
}

---

3. 결과

count를 세기 위한 반복문 안에 if(count>M) 조건문을 넣어서 틀렸다. 예제케이스 답이 제대로 나온 것부터 신기하다.