11501번 - 주식
이 문제의 질문중에 있는 방법으로해서 해결나는걸 보았는데
해당 방법으로는 1,000,000개의 값이 완전히 역순으로 되어 있을 때
재귀적으로도 오버플로우가 생기고 O(N^2)이 되어 시간상으로도 맞지 않을 것 같은데 성공이 됩니다.
제가 생각한 방법으로는
주식값의 0~i의 부분합을 미리 만들어놓고
주식값으로 내림차순 정렬을 하되 인덱스를 기록하고
인덱스의 최댓값을 갱신하면서 갱신된 (최대 인덱스 - 이전 최대 인덱스) * (부분합의 차이)를 더해서 최종 이익을 구하는 방법으로
퀵소트가 맞다면 O(N lg N)의 시간으로 풀리도록 했는데 시간초과가 납니다 ㅠㅠ
퀵소트에서 비교함수가 느린건지 왜 시간초과가 걸리게 되는지 알고 싶습니다 ㅠㅠㅠ
제 예상으로는
이 문제가 입력데이터가 엄청 큰데
이런 경우에는 cin, cout 으로 입출력을 하면 굉장히 느려집니다.
이것 때문에 시간초과가 난 것이 아닐까 싶네요.
말씀하신 '그' 코드는 scanf, printf 를 사용하고 있기도 하고요.
scanf, printf 로 입출력방식을 바꾸셔서 다시 제출해보세요.
댓글을 작성하려면 로그인해야 합니다.
godkad 8년 전
이 문제의 질문중에 있는 방법으로해서 해결나는걸 보았는데
해당 방법으로는 1,000,000개의 값이 완전히 역순으로 되어 있을 때
재귀적으로도 오버플로우가 생기고 O(N^2)이 되어 시간상으로도 맞지 않을 것 같은데 성공이 됩니다.
제가 생각한 방법으로는
주식값의 0~i의 부분합을 미리 만들어놓고
주식값으로 내림차순 정렬을 하되 인덱스를 기록하고
인덱스의 최댓값을 갱신하면서 갱신된 (최대 인덱스 - 이전 최대 인덱스) * (부분합의 차이)를 더해서 최종 이익을 구하는 방법으로
퀵소트가 맞다면 O(N lg N)의 시간으로 풀리도록 했는데 시간초과가 납니다 ㅠㅠ
퀵소트에서 비교함수가 느린건지 왜 시간초과가 걸리게 되는지 알고 싶습니다 ㅠㅠㅠ