kalmiaa   7년 전

뭐.. 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;

}

}


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


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


plzrun   7년 전

이 문제는 2차원 그래프가 그려지지 않아요.

4차원처럼 그려질 수도 있고 3차원처럼 그려질수도 있고... 그냥 그런거 자체가 적용이 안되는 문제네요.

3분탐색을 적용할 수 없습니다.



경우 몇개만 생각해보셔도 잠깐 착각하셨다고 생각하실거에용~!ㅎ

kalmiaa   7년 전

감사합니다. 풀기는 bfs로 무식하게 풀었는데요. 저 솔루션을 생각해봤었던 기억이 있는거 같네요. 다시 기억을 환기시켜서 정리해보겠습니다.

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