[C/C++ 백준 1756번] 피자 굽기 (Gold 5)

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

1756번: 피자 굽기

사실 왜 이분 탐색인지는 잘 모르겠다.

피자 오븐의 지름을 모두 받고, 해당 칸까지의 최소 지름을 저장하는 배열을 추가로 만든다.

그리고 직접 피자를 넣어가면서 어디까지 들어가는지 시뮬레이션 해주면 풀 수 있다(시간 복잡도 O(N)).

 

#include <cstdio>
#include <algorithm>
using namespace std;
long long int D, N, Oven[300001], Pizza[300001], real[300001];
int main(void){
	long long int mini = 1000000001;
	scanf("%lld %lld", &D, &N);
	for(int i=0; i<D; i++){
		scanf("%lld", &Oven[i]);
		mini = min(mini, Oven[i]);
		real[i] = mini;
	}
	for(int i=0; i<N; i++)
		scanf("%lld", &Pizza[i]);
	int cnt1 = D-1, cnt2 = 0;
	while(cnt1>=0 && cnt2<N){
		if(real[cnt1]<Pizza[cnt2]){
			cnt1--;
		}
		else{
			cnt1--;
			cnt2++;
		}
	}
	if(cnt2<N)
		printf("0");
	else
		printf("%d", cnt1+2);
}