이번에는 백준 6236번 용돈 관리 문제를 풀어보았습니다.
인출 금액 K가 작으면 자주 돈을 인출해야 하고, K가 커지면 더 적은 횟수의 인출로 여러 날을 버틸 수 있습니다.
즉, 특정 금액 K로 M번 이하의 인출이 가능한지를 판단할 수 있고, 가능한 K들 중 최솟값을 찾아야 하므로 파라메트릭 서치 + 이분탐색으로 해결하였습니다.
문제 설명
앞으로 N일 동안 사용할 금액이 주어집니다.
현우는 통장에서 돈을 인출할 때마다 항상 동일한 금액 K원을 인출합니다.
현재 가지고 있는 돈으로 그날 사용할 금액을 낼 수 없다면 남은 돈을 통장에 넣고 다시 K원을 인출합니다.
또한 정확히 M번 인출해야 하지만, 필요한 인출 횟수가 M보다 적다면 일부러 남은 돈을 넣고 다시 인출하는 것도 가능합니다.
따라서 중요한 것은 K원으로 M번 이하의 인출만으로 모든 날을 처리할 수 있는지입니다.
이 조건을 만족하는 최소 K를 구하는 문제입니다.
풀이 아이디어
가능한 인출 금액의 범위를 먼저 정합니다.
K는 하루에 사용하는 금액보다 작을 수 없습니다.
따라서 최솟값은
하루 사용 금액 중 최댓값입니다.
반대로 모든 날의 사용 금액을 한 번에 인출하면 무조건 가능하므로 최댓값은
모든 사용 금액의 합으로 둘 수 있습니다.
이 범위에서 mid를 인출 금액이라고 가정한 뒤 check_available(mid)를 통해 M번 이하의 인출로 모든 날을 처리할 수 있는지 확인합니다.
가능하다면 더 작은 금액도 가능한지 확인하기 위해 왼쪽 구간을 탐색하고, 불가능하다면 더 큰 금액을 탐색합니다.
코드
#include <bits/stdc++.h>
using namespace std;
int N,M;
vector<int> inp;
bool check_available(int money) {
int curr = money;
int cnt = 1;
for (int i=0; i<N; i++) {
curr -= inp[i];
if (curr < 0) {
cnt++;
curr = money-inp[i];
}
if (cnt > M) return false;
}
return true;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N >> M;
int low=INT_MIN,high,mid;
int sum = 0;
for (int i=0; i<N; i++) {
int money;
cin >> money;
inp.push_back(money);
low = max(low,money);
sum += money;
}
high = sum;
int ret = high;
while(low <= high) {
mid = (low + high) / 2;
if (check_available(mid)) {
high = mid - 1;
ret = mid;
} else {
low = mid + 1;
}
}
cout << ret << '\n';
return 0;
}풀이 흐름
-
N,M을 입력받습니다. -
각 날짜별 사용 금액을 저장합니다.
-
가장 큰 하루 사용 금액을
low로 설정합니다. -
전체 사용 금액의 합을
high로 설정합니다. -
low ~ high범위에서 이분탐색을 수행합니다. -
mid를 현재 인출 금액K라고 가정합니다. -
check_available(mid)를 통해M번 이하의 인출로 모든 날을 처리할 수 있는지 확인합니다. -
가능하다면 현재
mid를 정답 후보로 저장하고 더 작은 값을 탐색합니다. -
불가능하다면 더 큰 금액을 탐색합니다.
-
탐색이 끝난 뒤 최소 인출 금액을 출력합니다.
구현 포인트
1. 이분탐색의 최솟값
low = max(low,money);인출 금액 K는 적어도 하루 사용 금액 중 최댓값 이상이어야 합니다.
예를 들어 하루 사용 금액이 다음과 같다면
100
300
200K가 250이라면 300원이 필요한 날은 한 번 인출해도 해당 금액을 사용할 수 없습니다.
따라서 최소 후보는
300이 되어야 합니다.
2. 이분탐색의 최댓값
high = sum;모든 사용 금액의 합을 한 번에 인출하면 추가 인출 없이 모든 날을 처리할 수 있습니다.
따라서 전체 합은 항상 가능한 값이므로 이분탐색의 상한으로 사용할 수 있습니다.
예를 들어
100 + 300 + 200 = 600이라면 K = 600은 무조건 가능합니다.
3. 현재 인출 금액으로 가능한지 확인
bool check_available(int money)money를 인출 금액 K라고 가정하고 실제로 며칠을 버틸 수 있는지 순서대로 확인합니다.
먼저 처음 한 번 돈을 인출했다고 생각합니다.
int curr = money;
int cnt = 1;curr은 현재 가지고 있는 돈이고, cnt는 지금까지 인출한 횟수입니다.
4. 하루 사용 금액 차감
curr -= inp[i];매일 필요한 금액을 현재 가지고 있는 돈에서 차감합니다.
차감한 결과가 0 이상이라면 현재 돈으로 해당 날까지 처리할 수 있다는 뜻입니다.
5. 돈이 부족한 경우 재인출
if (curr < 0) {
cnt++;
curr = money-inp[i];
}현재 돈으로 그날 사용할 금액을 감당할 수 없다면 새롭게 money원을 인출합니다.
따라서 인출 횟수를 1 증가시킵니다.
새롭게 인출한 돈에서 오늘 사용할 금액을 바로 차감하여
curr = money - inp[i];로 설정합니다.
6. 인출 횟수가 M을 넘어가면 불가능
if (cnt > M) return false;현재 K로 모든 날을 처리하는 과정에서 인출 횟수가 M보다 많아진다면 해당 금액은 사용할 수 없습니다.
즉,
현재 K가 너무 작다.라는 의미입니다.
이 경우 이분탐색에서 더 큰 금액을 확인해야 합니다.
7. 정확히 M번이 아니라 M번 이하를 확인하는 이유
문제에서는 정확히 M번 인출해야 한다고 했습니다.
하지만 남은 돈이 충분하더라도 원한다면 다시 통장에 넣고 새롭게 인출할 수 있습니다.
따라서 최소 필요 인출 횟수가 M보다 작더라도 추가 인출을 일부러 만들어 정확히 M번으로 맞출 수 있습니다.
즉,
필요 인출 횟수 <= M이면 가능한 경우입니다.
따라서 check_available()에서는 cnt > M인 경우만 실패로 처리합니다.
8. 가능한 경우 더 작은 값 탐색
if (check_available(mid)) {
high = mid - 1;
ret = mid;
}현재 mid원으로 M번 이하의 인출이 가능하다면 mid는 정답 후보가 됩니다.
하지만 문제에서는 최소 금액을 구해야 하므로 더 작은 값에서도 가능한지 확인해야 합니다.
따라서
high = mid - 1;로 왼쪽 구간을 탐색합니다.
9. 불가능한 경우 더 큰 값 탐색
else {
low = mid + 1;
}현재 mid로는 인출 횟수가 너무 많이 필요하다는 의미입니다.
K가 더 커지면 한 번 인출한 돈으로 더 많은 날을 버틸 수 있으므로 더 큰 범위를 탐색합니다.
10. 이분탐색이 가능한 이유
인출 금액 K가 커질수록 필요한 인출 횟수는 증가하지 않습니다.
즉, 어떤 금액 K가 가능하다면 그보다 큰 금액도 항상 가능합니다.
가능 여부를 나열하면 다음과 같은 형태가 됩니다.
불가능 불가능 불가능 가능 가능 가능 ...따라서 처음으로 가능한 값을 이분탐색으로 찾을 수 있습니다.
이러한 형태의 문제를 파라메트릭 서치라고 볼 수 있습니다.
11. 정답 후보 저장
int ret = high;전체 사용 금액의 합은 항상 가능한 값이므로 초기 정답 후보로 둘 수 있습니다.
이후 가능한 mid를 발견할 때마다
ret = mid;로 갱신합니다.
더 작은 가능한 값을 계속 찾아가기 때문에 최종적으로 최소 K가 저장됩니다.
시간복잡도
check_available()에서는 N일을 한 번 순회하므로
O(N)의 시간이 필요합니다.
이분탐색은 금액 범위를 기준으로 진행하므로
O(log(sum))번 수행됩니다.
따라서 전체 시간복잡도는
O(N log(sum))입니다.
N이 최대 100,000이므로 충분히 해결할 수 있습니다.
