백준 BOJ 2343 - 기타 레슨

파라메트릭 서치는 몇번을 해도 ㄹㅇ 이 뇌절을 막을수가 없음

어떻게하는지 아직도 잘 ㅁㄹ겠다.

 

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

2343번: 기타 레슨

블루레이의 녹화 가능한 길이에 따라서 True/False 여부가 갈리는

이분탐색 문제였다.

M개로 쪼개는건 그냥 나이브하게 O(N) 에 처리가능.

파라메트릭이 상수가 많이붙어서그렇지 O(log1e9) 상수시간에 처리가 되고있는데

TLE를 받진 않을거같다.

 

 

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

ll n,m;
ll arr[123456] = {0};

ll search(ll s, ll e){
	ll mid = (s+e)/2;
	if(s>e) return s;
	
	ll cnt = 0;
	ll tmp = 0;
	for(int i=0; i<n; i++){
		tmp += arr[i];
		if(mid < tmp){
			tmp = 0;
			i--;
			cnt++;
		}
	}
	
	if(cnt < m) return search(s,mid-1);
	else        return search(mid+1,e);
}

int main(){
	cin >> n >> m;
	
	ll maxv = -1;
	for(int i=0; i<n; i++){
		cin >> arr[i];
		maxv = max(maxv, arr[i]);
	}
	cout << search(maxv, 1e9);
	return 0;
}

진짜 매번 한결같이

파라메트릭은 종료조건 (s>e) 짜는거랑

s, mid 로 할지

s, mid-1 로 할지

이거두개에서 맨날 뇌절침

틀리길래 무지성으로 long long 박았는데

오버플로우가 일어나고있는지는 잘 모르겠다.