[백준 1756] 피자 굽기

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

1756번: 피자 굽기

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int D, N; 
vector <int> oven;

// 피자반죽 N개
// 오븐의 깊이 D
// 오븐의 지름보다 크면 통과하지 못한다.

int min(int a, int b)
{
	return (a < b) ? a : b;
}

int search_bin(int st, int ed, int key)
{
	if (ed <= 0) //  오븐 깊이가 0 이하이면
		return -1;

	if (st - ed + 1 >= 0) // 탐색 종료 (시작점과 끝점이 1 차이)
	{
		if (oven[st] >= key) // 피자 도우 길이보다 오븐이 크면
			return st;
		else // 피자를 넣을 수 없음
			return -1;
	}

	int mid = (st + ed) / 2;

	if (oven[mid] >= key) // 피자 도우가 들어갈 수 있을 때
		return search_bin(mid, ed, key); // 다음 오븐 탐색
	else
		return search_bin(st, mid, key); // 이전 오븐 탐색
}

int main()
{
	cin >> D >> N;

	for (int i = 0; i < D; i++)
	{
		int r;
		cin >> r;
		oven.push_back(r);
	}

	int min_r = oven[0]; // 가장 처음 오븐의 지름
	for (int i = 1; i < oven.size(); i++)
	{
		oven[i] = min(min_r, oven[i]); // 오븐의 지름이 이전보다 크면 변경
		min_r = oven[i];
	}

	int deep = D;
	for (int i = 0; i < N; i++)
	{
		int r;
		cin >> r;
		deep = search_bin(0, deep, r);
	}

	cout << deep + 1;

	return 0;
}

 

처음 시도에 모든 경우의 수를 체크해보니 당연하게도 시간 초과가 떴다.

dp로 생각을 해보면

 

기본적으로 오븐의 모형이 위와 같다고 했을 때

실질적으로 오븐에서 사용 가능한 영역은 파란색과 같다.

오븐의 지름을 이전 지름과 비교해서 현재 지름이 이전 지름보다 크다면 이전 지름으로 변경하였다.

예시의 경우 [5, 6, 4, 3, 6, 2, 3] 이었던 오븐을 [5, 5, 4, 3, 3, 2, 2]로 변경시킨다.

이후로는 피자의 지름에 따라 이진탐색을 진행한다.

이진탐색 시에는 이미 피자를 넣은 뒤에 줄어든 범위로 다시 정의하여 재탐색한다.