#include <iostream>#include <vector>#include <ctime>usingnamespacestd;voidFENCE();intArea(intleft,intright,vector<int>vtr);intmaximum(inta,intb);intminimum(inta,intb);intmain(){intnTestCase;cin>>nTestCase;while(nTestCase--){//int start = clock();FENCE();//int end = clock();//double time = (double)(end - start);//cout << "Access Time : " << time / CLOCKS_PER_SEC << endl;}return0;}// main()voidFENCE(){intnFence;intnHeight;vector<int>vtrInput;cin>>nFence;//srand((unsigned)time(NULL));while(nFence--){//테스트케이스 입력cin>>nHeight;//테스트케이스 생성//nHeight = rand()%10000;//cout << nHeight << " ";vtrInput.push_back(nHeight);}//cout << endl << "MAXIMUM AREA : ";cout<<Area(0,vtrInput.size()-1,vtrInput)<<endl;vtrInput.clear();}// FENCE()intArea(intnLeft,intnRight,vector<int>nVtrHeight){// 좌극 == 우극일때 높이를 반환if(nLeft==nRight)returnnVtrHeight[nLeft];// 중간 경계면을 기준으로 분할intnMid=(nLeft+nRight)/2;intnMaxOne=maximum(Area(nLeft,nMid,nVtrHeight),Area(nMid+1,nRight,nVtrHeight));// 중간 경계면을 포함하는 넓이를 계산intnLow=nMid;intnHigh=nMid+1;intnHeight=minimum(nVtrHeight[nLow],nVtrHeight[nHigh]);// 좌우값 중 큰값과 경계면을 포함하는 두펜스의 넓이 중 큰 값을 저장nMaxOne=maximum(nMaxOne,nHeight*2);// 경계면을 좌극값과 우극값 사이에서 확장while(nLeft<nLow||nHigh<nRight){// 우측으로 확장할 공간이 있고 &&// ( 좌측으로 확장할 공간이 없거나 || 우측으로 확장하는 경우에 더 큰 높이값을 가져가는 경우 )if(nHigh<nRight&&(nLow==nLeft||nVtrHeight[nLow-1]<nVtrHeight[nHigh+1])){// 우측으로 확장++nHigh;// 확장한면에서 가장 낮은 높이값을 저장nHeight=minimum(nHeight,nVtrHeight[nHigh]);}// 좌측으로 확장할 공간이 있고 &&// ( 우측으로 확장할 공간이 없거나 || 좌측으로 확장하는 경우에 더 큰 높이값을 가져가는 경우 )else{// 좌측으로 확장--nLow;nHeight=minimum(nHeight,nVtrHeight[nLow]);}// (좌우값 중 큰값과 경계면을 포함하는 두 펜스의 넓이중 큰값) 과 경계면을 포함하는 면의 넓이중에 큰값을 저장nMaxOne=maximum(nMaxOne,nHeight*(nHigh-nLow+1));}returnnMaxOne;}// maximumArea()// 큰값을 반환intmaximum(inta,intb){if(a>b)returna;elsereturnb;}// max()// 낮은값을 반환intminimum(inta,intb){if(a<b)returna;elsereturnb;}// min()
책에 있는 알고리즘을 이용해서 풀었는데 TLE가 뜨네요
시간계산해보니 입력값이 20000개 일때 평균 6~9초정도 걸리는데 어느부분을 수정해야할까요?
cjdahrl
책에 있는 알고리즘을 이용해서 풀었는데 TLE가 뜨네요
시간계산해보니 입력값이 20000개 일때 평균 6~9초정도 걸리는데 어느부분을 수정해야할까요?
10년 전