백준(BOJ) 6236 용돈 관리 C++ 풀이

문제 링크: https://www.acmicpc.net/problem/6236

6236번: 용돈 관리

문제 풀이에 이용된 알고리즘: 이진 탐색, 파라메트릭 서치

 

주어진 상황에서 가장 최적의 값을 고르는 문제이므로, 아직 실력이 부족한 나는... 탐욕법을 떠올렸다.

 

하지만 입력의 크기를 보아하니, 탐색의 범위가 굉장히 크다는 점과 결국 확인해야할 것은 "1회 인출 시 금액"으로 1번째 날부터 n번째 날까지 생활이 가능한 지, 불가능한 지 결정하는 문제 같다고 생각하여 이진 탐색으로 접근하기로 하였다.

 

이진 탐색 풀이가 필요한 문제 중에, 특정 조건을 만족하는 값이 여러 개 등장하여, 그 중에서도 최적의 값을 골라야하는 문제가 있는데 이런 경우 "파라메트릭 서치"가 필요하다.

 

이진 탐색으로 범위를 좁혀 나갈 때 마다 무조건적으로 정답이 갱신되는 것이 아니라, 정답이 될 수 있는 후보군에서 정답을 골라낼 때 필요한 데, 이 문제에서도 인출 횟수가 m 이하이면 그 때의 k가 정답의 후보가 될 수 있다.

 

"m 이하"인 수 간에는 무엇이 더 적합한 지(m이 작을 수록 좋다, m이 클수록 좋다 등등) 주어진 조건이 없기 때문에, 정답은 k가 최소일 때 결정된다.

 

파라메트릭 서치를 구현하는 방법은 굉장히 간단하다. 이진 탐색에서, 범위 분할이 일어나기 전에 이전 정답을 기억하고 있도록 해주기만 하면 된다. (52번 라인)

 

이런 생각으로 이진 탐색에 추가로 파라메트릭 서치까지 적용하였으나, 사실 이 문제는 이진 탐색만으로도 정답 처리가 되는 문제인데, 아직 사고의 깊이가 얕아서 어떤 부분을 잘 못 생각했는 지 연구 중이다...

 

/* BOJ 6236 용돈 관리 */
/* 이진탐색, 파라메트릭 서치 */
#define _CRT_SECURE_NO_WARNINGS
 
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string.h>
 
#define endl '\n'
 
using namespace std;
 
typedef long long ll;
 
const int INF = 1e9;
int money[100001], n, m, ans = INF;
 
bool check_answer(int k)
{
    // 1~n번째 날까지, 인출 시 k만큼할 때 살아갈 수 있는 지
    int balance = 0; // 잔고
    int cnt = 0; // 인출 횟수
    int need = 0; // i번째 날을 살아가기 위해 필요한 예산
    for (int i = 1; i <= n; i++)
    {
        need = money[i];
        if (need > k) // 인출할 수 있는 금액보다 큰 예산이 필요하면 생활 불가
            return false;
 
        if (balance < need) // 필요 예산보다 잔고가 조금 적다면
        {
            balance = k - need; // 모든 돈을 넣고 k만큼 인출 후 소비
            cnt++; // 인출 횟수 증가
        }
        else // 잔고로 충분히 살아갈 수 있다면
            balance -= need; // 인출 없이 소비
    }
    return cnt <= m;
}
 
void binary_search(int left, int right)
{
    if (left > right)
        return; // 탐색 종료
 
    int k = (left + right) / 2;
 
    if (check_answer(k)) // k로도 살아갈 수 있다면
        ans = min(k, ans), binary_search(left, k - 1); // 조금 더 적은 금액을 인출하는 방식으로도 살아갈 수 있는 지 파악
    else // 한 번 인출 시 k로는 못 살아간다면, k 증가
        binary_search(k + 1, right);
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    //freopen("input.txt", "r", stdin);
 
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> money[i];
 
    binary_search(0, INF);
    cout << ans << endl;
 
    return 0;
}