글 읽기 - 피자 굽기.. 한계네요 ㅠㅠ

kookmin20103324 9년 전 0

이전에 들어온 피자보다 크기가 같거나 작으면 바로 윗칸에 쌓고

아닐 경우 찾아가며 하는 방식으로는.. O(DN) 이라 타임오버 뜨는걸 알면서도

도무지 O(D+N)으로는 방법이 안떠오르네요... ㅠㅠ

#include<iostream>
using namespace std;
 
int main()
{
    int d,n,p,p2=0,r,o[300000];
	cin>>d>>n;
	r=d;
	for(int i=0;i<d;i++)
		cin>>o[i];
	while(n--)
	{
		cin>>p;
		if(p<=p2)
		{
			r--;
			goto z;
		}
		for(int i=0;i<r;i++)
		{
			if(p>o[i])
			{
				
				r=i-1;
				break;
			}
		}
        if(r<0)
        {
            cout<<"0";
            return 0;
        }
		z:
		p2=p;
		continue;
	}
	cout<<r+1;
}

h0ngjun7 9년 전 0

스택을 쓰시면 됩니다. Linear 솔루션이 힘드시면 bit를 이용한 n log n 솔루션 쪽으로도 생각해보세요.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

피자 굽기.. 한계네요 ㅠㅠ

kookmin20103324 9년 전 0

h0ngjun7 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말