문제
N일 동안 매일 사용할 금액이 정해져 있다. 통장에서 정확히 M번 인출할 때, 인출 금액 K의 최솟값을 구하라. 남은 돈이 부족하면 남은 돈을 넣고 다시 K원을 인출한다.
입력
첫째 줄에 N, M, 이후 N개의 일별 사용 금액이 주어진다.
출력
인출 금액 K의 최솟값을 출력한다.
예제
| 입력 | 출력 |
|---|---|
7 5 100 400 300 100 500 101 400 | 500 |
풀이
매개 변수 탐색으로 "인출 금액 K로 M번 이내에 관리할 수 있는가?"를 판별한다.
- 하한은 일별 최대 사용액, 상한은 10억으로 이분 탐색한다
- 인출 금액 mid로 시뮬레이션: 남은 돈이 부족하면 새로 인출하고 횟수를 센다
- 인출 횟수가 M 이하이면 금액을 줄이고, 초과이면 늘린다
핵심 아이디어: 인출 금액이 클수록 횟수가 줄어드는 단조성을 이용한 매개 변수 탐색이다.
코드
package day449;
import java.io.*;
import java.util.*;
public class Day405BOJ6236용돈관리 {
static int N, M;
static int l = 1, r = (int) 1e9, ans = 0;
static int[] arr;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
arr = new int[N];
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(br.readLine());
l = Math.max(l, arr[i]);
}
while (l <= r) {
int mid = (l + r) / 2;
if (getCnt(mid) > M) {
l = mid + 1;
} else {
ans = mid;
r = mid - 1;
}
}
System.out.println(ans);
br.close();
}
static int getCnt(int mid) {
int remain = mid;
int cnt = 1;
for (int i = 0; i < N; i++) {
if (remain - arr[i] < 0) {
remain = mid;
cnt++;
}
remain -= arr[i];
}
return cnt;
}
}복잡도
- 시간: O(N log X)
- 공간: O(N)