pcgos1   2년 전

계속 틀렸다고 뜨는데,, 머가 문제인지 잘모르겟어요... 

혹시 틀린게 먼지만 한번 설명해주실분 ㅠㅠ

djm03178   2년 전

3 2

2 1 3

정답은 2입니다. 처음에 2 1에서 중앙값이 1이고, 그 다음에 1 3에서 중앙값이 1이기 때문이죠.

pcgos1   2년 전

감사합니다


pcgos1   2년 전

다시 수정해서 돌려봣는데, 먼가 2프로에서 틀렸어요. ㅠㅠ 가 뜹니다..

혹시 이거 푸신 분 중에서, 틀릴만한 반례같은거 아시는 분 있나요?

djm03178   2년 전

일단 답이 틀린 이유는 unsigned int로 모든 경우를 커버할 수 없어서입니다.

그런데 이건 long long을 쓰더라도, 시간초과가 날 알고리즘입니다. 루프를 O(N)번 돌면서 K개의 원소를 정렬하니 시간복잡도는 대략 O(N*KlgK)가 되겠죠. 최악의 경우 240억 정도 됩니다.

테케가 약해서인지 O(NK)로 짠 코드로 예전에 가까스로 통과시킨 적이 있었지만, 의도한 대로라면 O(NlgN)이나 O(NlgK) 시간에 푸는 알고리즘을 고려하셔야 합니다.

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