godkad   8년 전

이 문제의 질문중에 있는 방법으로해서 해결나는걸 보았는데

해당 방법으로는 1,000,000개의 값이 완전히 역순으로 되어 있을 때

재귀적으로도 오버플로우가 생기고 O(N^2)이 되어 시간상으로도 맞지 않을 것 같은데 성공이 됩니다.


제가 생각한 방법으로는

주식값의 0~i의 부분합을 미리 만들어놓고

주식값으로 내림차순 정렬을 하되 인덱스를 기록하고

인덱스의 최댓값을 갱신하면서 갱신된 (최대 인덱스 - 이전 최대 인덱스) * (부분합의 차이)를 더해서 최종 이익을 구하는 방법으로

퀵소트가 맞다면 O(N lg N)의 시간으로 풀리도록 했는데 시간초과가 납니다 ㅠㅠ


퀵소트에서 비교함수가 느린건지 왜 시간초과가 걸리게 되는지 알고 싶습니다 ㅠㅠㅠ

ntopia   8년 전

제 예상으로는

이 문제가 입력데이터가 엄청 큰데

이런 경우에는 cin, cout 으로 입출력을 하면 굉장히 느려집니다.

이것 때문에 시간초과가 난 것이 아닐까 싶네요.

말씀하신 '그' 코드는 scanf, printf 를 사용하고 있기도 하고요.

scanf, printf 로 입출력방식을 바꾸셔서 다시 제출해보세요.

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