kalmiaa   4달 전

뭐.. N이 100밖에 안되니까, 다 돌려도 억셉은 뜨겠지만,

삼분검색으로 시간을 줄여보려다 실패했습니다.


제가 이해하기로는

높이 1~max(인풋범위에서의 최대 input이겠죠?)

사이에서 각각의 안전한구역 덩어리 갯수는


1 -> 점점 증가 -> 최대치 -> 점점 감소 -> 0 

으로 간다고 이해했습니다. 2차원 그래프 처럼요.

그래서 3분 검색이 통한다고 보고 있는데, 계속 fail을 먹네요.


3분 검색은 아래와 같이 했습니다.


while(lo<hi)

{

   int mid1 = (lo*2+hi)/3;

   int mid2  =(lo+hi*2)/3;


if(dicision(mid1)<dicision(mid2)

  lo = mid1+1;

else

{

  hi = mid2;

}

}


손으로 대충 친거라 양해바랍니다..


어디서 빵꾸가 나는지 모르겠네요.. ;;


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