[일반] 이거 nlogn에 어케 함??

[익명(175.223)]

내 능지로는 n^2logn이 한계노

[ㅁ(141.223)]

얘내를 정렬했다고 해보자. n-2,n-1,n번째 막대로 삼각형을 만들 수 있다면 얘내가 답이겠지. 정렬했으니까. 만약 삼각형이 안만들어지면 어떤 결론을 내릴 수 있음? 잘 생각해봐.

[익명(121.184)]

아 알겠다 ㄳㄳ

[정신차리고빚2억갚는중(dcoutsidermed)]

qsort 긁고, 3번부터 n번까지 가장 큰 변이라 가정하고, i번째 확인할때 i-1, i-2번째만 삼각형되는지 확인하며 max값 갱신해가면 충분하지않을까영

[익명(182.210)]

삼각형 성립조건도 생각해야하지 않나?

[익명(175.223)]

그니까 정렬을 해놓고 끝에서 3개씩만 살펴보는거지 그거로 삼각형 성립조건이 안되면 제일 미지막 끝을 변으로 하는 삼각형은 절대 만들 수 없음

[정신차리고빚2억갚는중(dcoutsidermed)]

대충 틀려서 삭제했는데 구간 1, 2-3,4-7,8-15,16-31,32-63식으로 나누고 각각 카운팅해서 높은 구간부터 내려오면서 3개 있으면 거기서 끝, 2개 있으면 상위 구간에 1개 이상 있는지 확인하고 min, max, 2등max 확인하고 O(1)에 흘려보내고 하면 O(n) 삽가능인듯

[정신차리고빚2억갚는중(dcoutsidermed)]

한개 있어도 상위구간에 두개있으면 될수있으니까 그것도 체크하고

[정신차리고빚2억갚는중(dcoutsidermed)]

근데 다시 생각해보니까 틀린답이었음 ㅈㅅ

[정신차리고빚2억갚는중(dcoutsidermed)]

그런데 다시 생각해보니 두개있는 구간도 max min 최대차이로 밑 구간 max 랑 찾아서 비교하면 O(1) 가능하니 O(n) 되네 ㅈㅅㅈㅅ

[정신차리고빚2억갚는중(dcoutsidermed)]

그런데 또다시 생각해보니 틀린답이었음 ㅈㅅ 구간 111도 답이있네

[정신차리고빚2억갚는중(dcoutsidermed)]

O(n) == 10^6 이면 1, 2-3, 4-7,. ..... 구간 20개정도 필요 arr[20][4] 배정 1. 입력받으면서 2^n - (2^(n+1)-1) 구간 찾아서 arr[n][0] => 그 구간내 max값 저장, arr[n][1] => 그 구간내 2번째 max 저장, arr[n][2] => 그 구간내 min 저장, arr[n][4] => 그 구간내 개수 counting 2. 가장 높은 구간부터 내려가면서 개수 3개 이상인 t 구간이 있다면, 우선 answer = t구간 max, 2번째 max + 3번째 max(선형검색) 3. 다시 가장 높은 구간부터 t+1구간 긁어 내려가면서 2개 있는 경우 그 이하 구간으로 쭉 긁어내려가면서 가장 큰 수를 구한후 삼각형이 되는지 확인 4. 이어서

[익명(182.231)]

구간을 찾는데 로그시간이 소요되는거 아님? 결국 nlogn아닌가 - dc App

[정신차리고빚2억갚는중(dcoutsidermed)]

nloga

[익명(182.231)]

더손해잖어 a가 n보다훨씬큰데 - dc App

[정신차리고빚2억갚는중(dcoutsidermed)]

4. 다시 가장 높은 구간부터 t+1구간 긁어 내려가면서 1개 있는 경우 삼각형을 이루기 위해서는 그 아래 가장 큰 숫자 2개만 확인하면 충분 고로 O(n)

[정신차리고빚2억갚는중(dcoutsidermed)]

t구간은 3개 이상인 구간중 가장 높은 구간임

[천재지망생(drggreen222)]

정렬에 n log n이고 가장긴 빗변을 하나골랐을 때 삼각형 만들 수 있는지 확인하는데 log n 이니깐 nlogn 일 듯

[익명(175.223)]

무슨 책임?