[일반] 시간초과 어캐 고쳐야 할까...

[코로나(lchbest10)]

https://www.acmicpc.net/problem/2217

[백준 2217번]

이중포문 밖에 안되는데 시간초과 나는데 알고리즘을 뜯어 고쳐야됨?? 이렇게 틀릴때가 젤 멘붕이네

[익명(210.204)]

100000*100000=시간초과

[익명(211.170)]

ㅇㅇ 뜯어고쳐야지. n 이 최대 10^5이니 이중포문이면 10^10까지 갈 수 있으니까... 이건 당연 시간초과. 대충 10^8 안에 들게 만들어야한다고 보면댐

[익명(210.204)]

잘 생각해 보면 nlogn에 끝난다. 정렬 제외하면 O(n)에 마무리. 이미 정렬을 했는데 최소값을 찾아다닐 필요가 있을까?

[코로나(lchbest10)]

findMin이 pick개 만큼 줄을 선택해서 최솟값 구하는건데 그 과정 필요 없다는거임?

[익명(210.204)]

다시 보니 로직부터 잘못 됐네... 반례부터 찾아보자. 0~pick 중 최소값에(물론 정렬했으니 0이겠지만) pick+1개를 곱하면 그게 꼭 로프가 버틸 수 있는 최대 중량일까?

[익명(211.170)]

병목이 어디서 일어나나 생각 해보셈

[이상함(1.241)]

로직 이상타라는 님들 말 다시함 세겨보면 10 20 30 로프 세개로는 30 아님? 최소값x로프개수 아님? 정렬도 필요하지 않아 보임