BOJ 6236 - 용돈 관리

www.acmicpc.net/problem/6236

6236번: 용돈 관리

 

 

처음 문제를 읽었을때, 지문 내용이 잘 이해가 안됬는데, 

i번째 날에 사용할 금액과 K원 둘의 명확한 차이점과 사용방식이 헷갈렸다.

 

문제에서 배열로 주어지는 값들(N개의 수, arr[i])은 i번째 날에 쓸 돈이고,

K원은 통장에서 인출한 돈이다.

그리고 K원을 인출할 수 있는 횟수는 M번으로 제한되어 있다.

 

if (arr[i] <= k) 이면, i번째 날은 k원만 가지고 생활이 가능하기 때문에, 이때는 인출하지 않고

if (arr[i] > k) 이면, i번째 날이 k원만 가지고는 생활이 안되므로, 인출을 해야된다. 

 

즉 인출을 하는 시점은, 배열의 구간합(i번째 날부터 j번째 날까지 사용한 돈) 이 k원을 넘어갔을때,

인출을 한다고 볼 수 있다. (배열에서 구간을 나눈 시점)

 

문제의 예제에서

N = 7, M = 5 이며

int arr[7] = [100, 400, 300, 100, 500, 101, 400] 인데, 

답이 k = 500 이므로 500을 기준으로 나누면

(100, 400), (300, 100), (500), (101), (400) 이렇게 5개의 구간으로 나눌 수 있다.

 

k 가 500 보다 작다고 하면, 아무리 해도 정확히 5개의 구간이 나오지 않는다.

그리고 k 가 500 보다 큰 값이면, 5개 보다 적은 구간으로 나눌 수도 있고, 정확히 5개의 구간을 만들 수도 있다.

(문제에서 제시하는 것은 반드시 M개의 구간을 만들어 내야하므로 k의 최소값으로만 답이 나오게됨)

 

 

문제는 k 의 범위를 어떻게 잡아내느냐이다.

단순하게 배열 전체를 돌면서

k 의 범위는, 최소값은 1 이고, 최대값은 배열 전체의 합으로 볼 수 있는데, 

k 의 금액을 1원부터 하나씩 늘리면서 최대값으로 확장하는 이중 포문 방식은 시간초과가 나기 때문에 사용이 불가능하다. (O(NK))

 

log 단위로 시간복잡도를 줄이기 위해 k 를 탐색할때 이분 탐색을 사용한다. 

 

(다른 사람들 풀이를 보면 k 의 범위를  "배열의 최댓값" <= k <= "배열 전체의 합" 으로 잡아서 푼 경우도 있었다. 이게 좀더 양을 줄이는 방법이 될 듯하다

참고 : blog.naver.com/PostView.nhn?blogId=crm06217&logNo=222019416769&categoryNo=23&parentCategoryNo=0&viewDate=&currentPage=1&postListTopCurrentPage=1&from=postView)

[백준 6236번] 용돈 관리, 이분 탐색 (Binary Search) 기초 (Python 코드 첨부, 난이도: Silver 3)

 

 

-c++

#include <iostream>
 
#define MAX 100001
#define INF 987654321
 
using namespace std;
 
int n, m, sum;
int answer = INF;
int arr[MAX];
 
bool check(int mid) { // mid 는 인출 금액 k 를 의미함 
    int cnt = 1, temp = mid;
    
    for (int i = 0; i < n; ++i) {
        if (arr[i] > mid) return false;  // 인출 금액보다 쓸 금액이 더 클때 
        
        if (temp < arr[i]) { // temp 는 배열 구간을 나누기 위한 변수임 
            temp = mid;
            cnt++;
        } 
        temp -= arr[i];
    }
    return cnt <= m;
}
 
void search() {
    int left = 1, right = sum;
    
    while(left <= right) {
        int mid = (left + right) / 2;
        
        if (check(mid)) {
            // 인출 금액이 더 큰 경우 더 적은 인출금액으로 좁히기
            right = mid - 1;
            answer = min(answer, mid); // 인출금액이 i번째 금액이상이어야 생존가능 
        } else {
            // 인출 금액이 더 작은 경우 더 큰 금액으로 늘리기 
            left = mid + 1;  
        }
    } 
}
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
        sum += arr[i];
    }
    
    search();
    cout << answer;
    
    return 0;
}