2468번 - 안전 영역
뭐.. 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;
손으로 대충 친거라 양해바랍니다..
어디서 빵꾸가 나는지 모르겠네요.. ;;
이 문제는 2차원 그래프가 그려지지 않아요.
4차원처럼 그려질 수도 있고 3차원처럼 그려질수도 있고... 그냥 그런거 자체가 적용이 안되는 문제네요.
3분탐색을 적용할 수 없습니다.
경우 몇개만 생각해보셔도 잠깐 착각하셨다고 생각하실거에용~!ㅎ
감사합니다. 풀기는 bfs로 무식하게 풀었는데요. 저 솔루션을 생각해봤었던 기억이 있는거 같네요. 다시 기억을 환기시켜서 정리해보겠습니다.
댓글을 작성하려면 로그인해야 합니다.
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;
}
}
손으로 대충 친거라 양해바랍니다..
어디서 빵꾸가 나는지 모르겠네요.. ;;