[3w] 이진탐색, parametric search

이진탐색과 parametric search의 reference
백준 문제
1. dp 복습 문제
아이디어

코드

#include <iostream>
#include <vector>
using namespace std;
vector<int> edge, price;
int N;
unsigned long long dp[100001];
int main() {
	cin >> N;
	edge.push_back(-1); price.push_back(-1); //[0]번 쓰레기값으로 채우기
	for (int i = 0; i < (N - 1); i++) {
		int num; cin >> num;
		edge.push_back(num);
	}
	for (int i = 0; i < N; i++) {
		int num; cin >> num;
		price.push_back(num);
	}
	dp[1] = 0;
	int cheapNode, cheapPrice = price[1];
	for (int i = 2; i <= N; i++) {
		if (price[i - 1] < cheapPrice) cheapPrice = price[i - 1];  //다음 인덱스로 가기 전, 이전 인덱스까지 가장 저렴한 가격의 기름 저장
		dp[i] = (unsigned long long)dp[i - 1] + (unsigned long long)((unsigned long long)cheapPrice * edge[i - 1]);
	}
	cout << dp[N];
	return 0;
}

2. parametric search
아이디어

코드

#include <iostream>
#include <vector>
using namespace std;
int N, M;
vector<int> garosu;
bool sol(int height) {
	if ((garosu[0] - height) > 0 || (garosu[M - 1] + height-1) < (N - 1)) return false;
	else return true;
}
int parametric(int left, int right) {
	if (left == right) {
		return left;
	}
	int mid = (left + right) / 2;
	if (sol(mid)) return parametric(left, mid);
	else return parametric(mid + 1, right);
}

int main() {
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int x; 
		cin >> x;
		garosu.push_back(x);
	}
	int maxHeight = 0;
	for (int i = 0; i < M-1; i++) {
		int minus = garosu[i + 1] - garosu[i];
		int nowHeight;
		if (minus % 2 == 0) nowHeight = minus / 2;
		else nowHeight=((minus / 2) + 1);
		if (maxHeight < nowHeight) maxHeight = nowHeight;
	}
	if (maxHeight == 0) maxHeight = 1;
	int result=parametric(maxHeight, N);
	cout << result;
	return 0;
}

3. 이진탐색 문제
아이디어

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N,C, maxInput, minInput=2100000000, near[200001];
vector<int> input;
/*
bool pandan(int mid){
    int start=minInput;
    for(int i=0;i<(C-1);i++) {
        if((start+mid)>maxInput) return false;
        start=near[start+mid];
        if(start==-1) return false;
    }
    return true;    
}
*/
bool pandan(int mid){  //집의 위치 정렬한 후 최근에 와이파이 설치한 곳부터 현재 순회중인 집의 위치까지의 거리가 mid이상이면 와이파이 설치하는식으로 판단
    int start=input[0];
    int cnt=1;  //제일 앞의 집에 와이파이 설치 -> 기본 1개로 시작
    for(int i=1;i<N;i++){
        if((input[i]-start)>=mid){
            cnt++;
            start=input[i];
        }
    }
    if(cnt>=C) return true;
    else return false;
}

int parametric(int left, int right){
    if(left==right) return left;
    int mid=(left+right+1)/2;
    if(pandan(mid)) return parametric(mid, right);
    else return parametric(left, mid-1);
}

int main(){
    cin>>N>>C;
    for(int i=0;i<N;i++){  //입력값 처리
        int n; cin>>n;
        if(n>maxInput) maxInput=n;  
        if(n<minInput) minInput=n;
        input.push_back(n);
    }
    sort(input.begin(), input.end());
    /*
    //여기부터 near벡터에 가장 가까우면서 더 멀리있는 집의 위치를 저장
    fill(near, &near[200001], -1);
    int lastH=0;
    for(int i=0;i<N;i++){
        int n=input[i];
        for(int j=lastH;j<=n;j++) near[j]=n;
        lastH=n+1;
    }
    */
    cout<<parametric(1, maxInput);
}