[c++] 6236번: 용돈 관리

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

6236번: 용돈 관리

문제 요약

N일 동안 사용한 금액을 M번만 통장에서 돈을 인출.
K원을 인출하는데 M번을 맞추기 위해 남은 금액이 그날 사용할 금액보다 많아도 남은 금액은 통장에 집어넣고 다시 K원을 인출.
돈을 아끼기 위해 인출 금액 K를 최소화. 최소 금액 K는?

범위

금액을 사용할 기간 N (1 ≤ N ≤ 100,000)
통장에서 금액을 인출할 횟수 M (1 ≤ M ≤ N)
이용할 금액  (1 ≤ 금액 ≤ 10000)

---

 

문제를 해석하다보면 너무 많은 것을 생각해서 이상한 길로 빠지는 경우가 있다. 문제에 없는 조건을 내가 추가한다거나 이런 경우에 이런 것도 포함해야 하는 건가 하는 의문을 가질 때가 있는데 이럴 땐 그냥 문제를 처음부터 다시 읽고 필요없는 부분은 빼버리는 게 낫다. (원하는 답과 관련없는 조건) 이 문제에서는 "남은 금액이 사용 금액보다 크다면 남은 금액을 통장에 다시 넣고 K원을 인출하는데, 통장에는 얼마가 있지?" 이런 식으로 딴 길로 새버렸다. 정신을 차리고 문제를 다시 읽고 목적이 무엇인가를 생각해보니

최소 금액 K로 M번 인출이 가능한가?

 

에 대한 질문에 YES라고 답할 최소 금액 K를 구하면 된다! 

 

 

예제를 보면서 쉽게 생각해보자!

만약 500원이 최소 인출 금액이라면, 1번째 날에 한번 인출(cnt=1)하고 1일(100), 2일(400)에 돈을 쓰고 3번째 날에 인출(cnt=2)한다. 

3일(300), 4일(100)에 돈을 쓰고 5일(500)에는 남은 금액이 100 이므로 쓸 돈이 모자라기 때문에 5번째 날에 인출(cnt=3)한다. 

5일에 500을 모두 사용했으므로 6번째 날에 인출(cnt=4)하고 7일(400)에는 남은 금액이 299 이므로 쓸 돈이 모자라기 때문에 7번째 날에도 인출(cnt=5)을 한다. 

 

//6236번: 용돈 관리
#include <iostream>
#include <algorithm>
typedef long long int ll;
using namespace std;
int n, m, x[100002], _max = -1;

void input(){
    cin >> n >> m;
    for(int i=0; i<n; i++) {
        cin >> x[i];
        _max = _max < x[i] ? x[i] : _max;
    }
}

bool calc(int k){
    int cnt = 1, sum = 0;
    for(int i=0; i<n; i++){
        if(sum + x[i] > k){ //최소 인출 금액을 초과하면
            cnt++;
            sum = x[i]; //최소 인출 금액을 초과했으므로 이 금액의 날짜부터 다시 시작(인출)
        }else{
            sum += x[i];
        }
    }
    return cnt <= m;
}

void solution(){
    int L = _max, R = 1000000000, ans = 0;
    while(L <= R){
        int mid = (L+R)/2;
        if(calc(mid)){
            ans = mid;
            R = mid - 1;
        }else{
            L = mid + 1;
        }
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(0); cout.tie(0); cin.tie(0);
    input();
    solution();
    return 0;
}

 

 

 

💡공부 및 기록용 블로그이므로 오류가 있을 수 있습니다. 만약 문제에 오류나 오타가 있다면 댓글로 알려주세요➿
     언제나 환영합니다. 감사합니다. 화이팅!☃️