[백준/C언어] 6236번 용돈 관리

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

6236번: 용돈 관리

 

• 문제 해결 방향

- 함정에 잘 빠질 수 있는 부분이 전날에 용돈을 사용하고 남았다면 그것을 그대로 사용하면서 인출을 추가하여 같이 쓸 수 있는 의미가 아니다.
 - 필요한 소요금액을 사용하고 돈이 남았더라도 다음날에 사용할 필요 금액보다 남은 금액이 적다면, 내 통장 계좌에 다시 남은돈을 집어 넣고 인출금액만 빼서 써야한다.
- 따라서 애초에 인출 금액의 단위보다 더 큰 금액을 사용해야 하는 날이 존재한다면, 애초에 불가능한 인출 금액이 된다. 
- 인출을 할 수 있는 횟수가 정해져 있는데, 이것을 소진하기 전까지 정해진 인출 금액으로 모든 날에 무리 없이 소비가 가능하다면 가능한 인출 금액이 되는 것임
- 문제를 잘 읽어 보면, 인출 횟수가 남았더라도 이유 없이 계좌에 돈을 넣었다 뺐다 하면서 횟수를 차감할 수 있으므로 마지막날을 기준으로 인출 횟수가 남는 것은 큰 문제가 되지 않으며, 인출 가능 횟수가 부족해지는 것이 문제가 된다. 
- 이렇게 이진탐색을 이용해 금액을 찾아가면 된다.

 

 

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

#define MAX_N (100000)

int N, M;
int need[MAX_N];

void Input_Data(void) {
    int i;
    scanf("%d %d", &N, &M);
    for (i = 0; i < N; i++) {
        scanf("%d", &need[i]);
    }
}



int Is_possible(int m)  //이진탐색에서 해당 값이 가능한지, 불가능한지 판단하기 위한 함수
{
    int max = 0;
    for (int i = 0; i < N; i++)
    {
        if (need[i] > max) max = need[i]; //돈을 사용해야 하는 날 중에 가장 많이 써야하는 날의 필요양 정하기
    }

    if (m < max) return 0; //전날에 사용한 돈이 남더라도 계좌에 돈을 넣고 다시 빼야하므로 하루에 사용할 수 있는 최대 금액은 인출 금액임

    int now_credit = 0;
    int S = M; //인출 횟수를 사용하기 위해 다른 변수로 받아놓음
    for (int i = 0; i < N; i++)
    {
            
        if (now_credit < need[i]) //만약 현재 지갑에 남은 돈이 오늘 사용할 양보다 적다면
        {
            now_credit = m; //남은 돈은 다시 계좌에 집어넣어 0으로 만들고 새로 인출하여 m상태가 된다.
            now_credit = now_credit - need[i]; //오늘 사용할 돈을 반영하여 남은돈 계산
            S--; //인출 횟수 차감
        }
        else //지갑에 남은 돈이 오늘 사용할 양보다 많다면 그대로 사용하고 인출 횟수는 차감하지 않고 유지한다.
        {
            now_credit = now_credit - need[i]; 
        }
    }

    if (S >= 0) return 1; //만약 인출횟수가 남더라도 넣었다 뺐다 하면서 강제로 차감할 수 있으므로 차감가능횟수가 부족한게 문제이지 남는다고 문제가 안됨
    else return 0; //차감횟수가 주어진 차감횟수보다 많이 사용되면 불가능한 인출 금액임

}


int solve()
{

    int s = 0; int e = 1000000000; int sol = -1; //k의 범위는 10000이고 N일의 범위는 10000일이므로 10억을 범위로 잡음

    while (s <= e)
    {
        int m = (s + e) / 2;
        if (Is_possible(m))  //최소 인출 금액을 찾는 것이므로 최소값을 찾는 이진탐색을 사용
        {
            sol = m;
            e = m - 1;
        }
        else
        {
            s = m + 1;
        }
    }
    
    return sol;
}


int main(void) {
    int sol = -1;

    // 입력 받는 부분
    Input_Data();

    // 여기서부터 작성


    sol = solve();

    // 출력하는 부분
    printf("%d\n", sol);

    return 0;
}​