백준 1756 <피자 굽기>

문제 풀이

1. 오븐의 깊이를 위에서부터 넣으면서 현재까지 가장 좁은 길이를 다음 깊이에 넣는다.

2. 이분 탐색을 이용해서 피자를 어디 위에 올릴 수 있는지 알아낸다.

3. 피자를 올린 깊이와 맨 위의 깊이 사이를 계속해서 이분 탐색한다.

4. 올릴 수 없다면 음수가 될 것이다.

 

생각이 많이 필요했던 문제 중 하나이다. 골드 5라는 수준을 못 믿었던...

 

 

일단 문제를 보면 완 탐으로 풀면 되지 않을까? 했지만 그렇게 되면 300000^2 이므로 당연히 터진다.

 

그렇다면 생각할 부분은 어떻게 자신보다 크거나 같은 아래쪽에 넣을 수 있을까를 먼저 생각해야 한다.

 

문제 풀

 

결국은 위에서 넣었을 때 자신보다 작은 지점 바로 위층에 쌓이게 되는 것이다.

이 지점을 찾는 것은 의외로 생각만 한다면 간단해질 것이다.

 

그렇게 한 다음 이분 탐색으로 어디 부분에 쌓을 수 있는지 체크를 해주면 되는 것이다.

 

하지만 이 부분에서 고려해줄 것은 이전의 이분 탐색은 오름차순이었다면 이 배열은 내림차순이므로 조금 생각이 필요하다.

 

이렇게 하게 되면 finish 값은 지금 넣을 피자 크기보다 작은 층중 꼭대기를 가르칠 것이므로 -1 해준다.

 

이렇게 이분 탐색으로 문제가 풀린다.

 

이분 탐색에 관한 문제는 자주 나오기 때문에 알아두는 것이 좋다.

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	static int d,n,start,finish;
	static int pizza[],num[];
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(br.readLine());
		d=Integer.parseInt(st.nextToken());
		n=Integer.parseInt(st.nextToken());
		num=new int[d];
		pizza=new int[n];
		st=new StringTokenizer(br.readLine());
		int min=Integer.parseInt(st.nextToken());
		num[0]=min;
		for(int i =1;i<d;i++) {
			int next=Integer.parseInt(st.nextToken());
			min=Math.min(min,next);
			num[i]=min;
		}
		st=new StringTokenizer(br.readLine());
		for(int i =0;i<n;i++) {
			pizza[i]=Integer.parseInt(st.nextToken());
		}
		start=0;
		finish=d;
		for(int i=0;i<n;i++) {
			find(pizza[i]);
			finish--;
			if(finish<0) {
				break;
			}
			start=0;
		}
		System.out.println(finish+1);
		
	}
	private static void find(int i) {
		// TODO Auto-generated method stub
		while(start<finish) {
			int mid=(start+finish)/2;
			if(num[mid]<i) {
				finish=mid;
			}
			else {
				start=mid+1;
			}
		}
	}

}