[알고리즘 개념] 파라메트릭 서치

찾았다 요놈

문제 조건에서 10억, 20억 같은 녀석이 있으면. 이분 탐색, 파라메트릭 서치를 의심하자🤔
binary search에서 주의해야 할 점은 항상 lo 와 hi 의 초기값 설정이다. 무엇이 최소고 최대인지를 판별해주어야 한다.

파라메트릭 서치(Parametric Search)란?

• 1부터 n까지의 자연수의 합이 s이하인 경우 중 가능한 n의 최댓값을 구하는 프로그램인 경우를 알아보자.
  아주 간단하게 해결된다!

---

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
#define MAX_S 2e9+1
ll s;
ll ans =0;

int main(){
    cin >> s;
    ll lo = 1; ll hi = MAX_S; ll mid;
    while(lo <= hi){
        mid = (lo+hi)/2;
        if(mid*(mid+1)/2 > s){
            hi = mid-1;
        }
        else {
            lo = mid+1;
            ans = max(ans, mid);
        }
    }
    cout <<ans;
}

(🌟)숫자 합 최대 되도록 파티션 치기

다음과 같이 10개의 숫자가 주어졌을 때,
칸막이를 최대 4개를 쳐서 각 칸막이를 경계로 나뉜 숫자들의 합들 중
최댓값이 최소가 되도록 하는 프로그램을 작성해보세요.

주어진 10개의 숫자 : 2 3 5 5 3 1 6 5 7 3

만약 다음과 같이 나누면 
2 3 | 5 | 5 3 | 1 6 | 5 7 3

각 구간내 숫자의 합이 합이 5, 5, 8, 7, 15가 되므로 
이 중 최댓값은 15가 되지만,

다음과 같이 나누면
2 3 | 5 5 | 3 1 6 | 5 | 7 3

각 구간내 숫자의 합이 5, 10, 10, 5, 10가 되므로
최댓값이 10이 됩니다.

따라서 10이 답이 됩니다.

1. 결정 문제
2. 최적화 문제

#include <iostream>
using namespace std;
typedef long long ll;
#define INT_MAX 100001
int arr[10]={2, 3, 5, 5, 3, 1, 6, 5, 7, 3};
int n=10;
int ans=INT_MAX;

bool isPossible(int cur_sum){
    int sum=0;
    int partitions=0;
    for(int i = 0; i < n; i++){
        if(arr[i] > cur_sum) return false;
        sum += arr[i];
        if(sum > arr[i]) {
            partitions+=1;  // 칸막이 설치 후
            sum = arr[i]; // 다시 합 집계 시작
        }
    }
    if(partitions <= 4) return true;
    return false;
}

int main() {
    int mid; int lo=1; int hi=0;
    for(int i = 0; i < 10; i++) hi+=arr[i];
    while(lo <= hi){
        mid= (lo+hi)/2; 
        if(!isPossible(mid)) {
            lo = mid+1;
        } 
        else {
            hi = mid-1;
            ans = min(ans,mid);
        }
    }
    cout <<ans;
    return 0;
}