[백준] 6234번 : 용돈 관리 (도식화 -> 로직 -> 코드)

 

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

 

용돈 관리 문제의 경우 번역이 모호한 것이 있어 문제 이해를 하는데 오래 걸렸습니다. 

 

금액의 경우 총 4가지 종류가 있습니다. 

1. 통장 금액

2. 인출 금액 K 

3. 현우가 하루 당 사용할 금액 a[i] 

4. 잔액 =  인출 금액 K - 현우가 하루 사용할 금액 a[i] 

 

TIP 

여기서 1. 통장 금액의 경우 금액이 무한정라고 생각해야 문제가 이해가 됩니다.

 

목표

M번 인출할 수 있을 때 인출 금액 K의 최솟값을 구해야합니다.

 

도식화 

예시를 통해 문제를 이해해봅시다. 

1)  N = 2일 동안 M = 3 번 인출할 수 있고, 인출 금액(K)가 500원일 때, 현우가 2일 동안 100원, 400원이 필요하다면

 

1일 때 인출된 금액 500원에서 100원을 소비하고 남은 금액이 400원이 됩니다. 이 남은 금액을 가지고 다음 날 사용할 금액에서 빼야합니다. 

인출을 1번 했을 때, 모든 요일의 금액을 충당할 수 있기 때문에 조금 더 인출된 금액을 상향 시킬 수 있겠죠? 물론 2일차일 때 이미 남은 금액(400원)으로 2일차에서 필요한 금액 400원을 충당할 수 있지만 다시 인출을 할 수 있습니다. 그래서 M = 2를 맞출 수 있습니다. 

 

인출 금액 K = 500원을 더 작게 만들어 봅시다. K = 400원으로 낮춘다면 

1일 때 인출된 금액 400원에서 1일차에 100원을 소비하고 남은 금액은 300원이 됩니다. 남은 금액 300원으로는 2일차의 400원을 충당할 수 없습니다. 그러면 2일차 당일에 인출을 1회 합니다. 그럼으로써 실제로 인출한 횟수는 2회가 됩니다. 

 

주의사항은 인출된 금액은 한번 더 인출한다고 해서 누적되지 않습니다. 

지문에서 " 모자라게 되면 남은 금액은 통장에 집어넣고 다시 K원을 인출한다. " 라고 명시되어있기 때문입니다. 이 말은 인출 금액 K 400 원으로 남은 금액 300원을 담는 변수를 초기화 해야하는 것을 의미합니다. 

그럼 인출 금액 400원으로 2번 인출이 가능해집니다. 하지만 이것이 최소 금액인지는 정확히 모릅니다. 

 

 

로직 

인출 금액이 가질 수 있는 값의 범위를 구해서 시작값부터 끝 값까지 for 반복문으로 선형 탐색하면서 최소 인출 금액 K를 구할 수 있습니다. 하지만 [시작값, 끝값] 범위가 10억을 넘어간다면 O(N)시간 초과가 발생합니다. 매우 큰 범위의 탐색을 하는 경우 "이분 탐색"을 하면 O(logN)의 복잡도로 줄어들게 됩니다.

 

주의 사항

- 이분 탐색으로 탐색할 범위는 입력으로 받은 현우의 사용 금액이 아닙니다. -> 정렬이 필요없는 이유

• 이분탐색 문제임에도 ‘현우가 이용할 금액’이 저장된 배열을 정렬하지 않는 이유는 이미 lo, hi가 탐색하는 배열은 등차가 1인 수열이므로 정렬을 할 필요가 없기 때문입니다. 

→ low, high가 탐색하는 배열에 저장된 값이 어떤 값인지 확인

• low와 high가 탐색하는 배열은 입력으로 받은 ‘현우가 이용할 금액’이 저장된 배열이 아니라 d = 1 인 등차수열입니다. 

 

이분 탐색에 필요한 low, high 의 범위를 구해봅시다. 

1. low

low = max(현우가 입력받은 사용금액) 입니다. 문제에서 '인출 금액 K < 하루 사용 금액 a[i] '인 경우 "남은 금액이 그날 사용할 금액보다 많더라도 남은 금액은 통장에 집어넣고 다시 K원을 인출할 수 있다." 라고 했기 때문입니다. n일차에 1번 인출 금액 K원을 가지고 현우가 n일차에 필요한 금액을 "무조건 차감"하게 됩니다. 

 

2. high

high = 10000 vs. high = 1,000,000,000 (10억)중 무엇일까요?

정답은 high = 10억 입니다. 

 

high = 10,000 이 틀린 이유

최악의 경우를 고려할 때 m 의 값을 고려해야합니다. 금액의 범위의 상한선이 되는 것이 아닙니다. (1 ≤ 금액 ≤ 10,000) m = 1 번 인출, n = 100,000일, 현우가 n일 동안 10,000원씩 필요하다면 총 1,000,000,000원이 인출금액이어야 성립합니다.

 

 

 

코드

#include<bits/stdc++.h>
using namespace std;
typedef long long ll ;
ll a[100'004], n, m, ret = 1e18, mx = -1e18;
bool check(ll e_val) {
    int temp = e_val; 

    ll cnt = 0;
    for(ll i = 0; i < n; i++) {
        if(a[i] > e_val) { // 하루 가용 금액(K)로 사용 불가능한 경우 
            cnt++; 
            e_val = temp; 
        }
        // 하루 가용 금액(K)로 소비가 가능한 경우 
            e_val -= a[i]; 
        
    }
    cnt++;
    return cnt <= m; 
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m; 
    for(ll i = 0; i < n; i++) {
        cin >> a[i];
        mx = max(a[i], mx);
    }

    ll lo = mx;
    ll hi = 1'000'000'004; 

    while(lo <= hi) {
        ll mid = (lo + hi) / 2; 

        if(check(mid)) {
            hi = mid -1; 
            ret = min(ret, mid);

        }
        else {
            lo = mid + 1; 
        } 
    }

    cout << ret << '\n';
    return 0;
}

 

 

실행결과