백준 6236 용돈 관리 c++ [컴공과고씨]

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

6236번: 용돈 관리

 

문제 간단 정리

돈을 통장에서 인출하는 횟수를 정해놓고 씀.

인출한 금액에서 하루 하루 금액을 정해놓고 사용.

인출한 금액을 쓰다가 모자른 경우 남은 금액 통장에 넣고 다시 아까 정해놓은 인출 금액을 꺼내서 씀.

이때 인출하는 금액을 최소가 되도록 구해라.

인출하는 횟수가 문제에서 주어진 횟수보다 크면 안됨.

하지만 인출하는 횟수가 적은 것은 상관없음

이유는 문제에서 인출하는 횟수를 맞추기 위해서 금액이 부족하지 않더라도 통장에 입금 후 다시 인출하는 것을 허용함.

 

문제 해결 방법

가장 떠올릴 수 있는데 금액을 1부터 쭉 해보는 것일 수 있는데 이러면 당연히 시간초과가 날 것입니다.

그래서 이분 탐색을 사용하여서 풀어주면 됩니다.

최소값을 1로 하고 최대값은 하루마다 쓰는 금액을 다 더한 것으로 하여서 이분탐색을 해주면됩니다.

이유는 딱 한번 인출해서 모든 날을 쓸 수 있는 금액이 최대값이기 때문입니다.

 

이분 탐색 구현 방법

먼저 최소와 최대의 평균을 구해 그것을 인출 금액으로 정하고 갑니다.

인출 횟수 초기값은 1입니다.

현재 남아있는 금액 total에 인출 금액을 넣어줍니다.

그리고 먼저 하루 쓸 금액이 인출 금액보다 크다면 성립이 안되기때문에 바로 하루마다 체크하는 것을 그만 두고 다른 인출 금액을 정해줍니다. 

이때 기존 금액보다는 당연히 크도록 잡아야하기 때문에 low = mid + 1로 해줍니다.

다음 확인할 것은 total이 하루쓸 금액보다 작다면 돈이 부족한 것이므로 total에 인출 금액을 넣어주고 인출 카운트를 해줍니다. 그 후 total에서 하루쓸 금액을 빼줍니다. 이렇게 하루마다 확인 작업을 해준 후 만약 정한 횟수보다 많이 인출 했다면 인출 금액을 늘려줍니다. 그것이 아니라면 인출 금액을 저장해두고 금액을 작게 해서 탐색합니다.

 

 

전체코드

#include <iostream>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    int money[100002]; // 하루마다 쓸 금액 저장
    int a, sum = 0;
 
    for (int i = 0; i < n; i++){
        cin >> a;
        sum += a; // 최대값
        money[i] = a;
    }
    int result = 0;
    int low, mid, high;
    low = 1; // 최소값
    high = sum; // 최대값
    int total; // 현재 남은 금액
    while(low <= high){
        mid = (low + high) / 2; // 인출 금액
        total = mid; // 인출 금액으로 초기화
        bool pass = true; // 성립 가능한지
        int cnt = 1; // 인출 횟수 1로 시작
        for (int i = 0; i < n; i++){
            int day_money = money[i];
            if(day_money > mid){ // 하루쓸 돈이 인출 금액보다 크면 성립x
                pass = false; 
                break;
            }
            if(day_money > total){ // 하루쓸 돈이 남은 돈보다 큰 경우
                total = mid; //돈을 인출
                cnt++; // 인출 횟수 카운트
            }
            total -= day_money; // 하루에 쓸 돈 차감       
        }
        if(!pass || cnt > m){ // 인출 횟수가 많거나 성립x
            low = mid+1; // 인출 금액 늘려줌
        }else{ 
            result = mid; // 인출 금액 저장
            high = mid-1; // 인출 금액 낮춰서 탐색
        }
    }
 
    cout << result << endl; // 출력
    return 0;
}

 

체감 난이도	걸린시간	후기	사용 알고리즘
중하	1h	최대값 하루 쓸 금액의 최대값으로 잘못설정하여 오래걸림	이분탐색