ylee399   2년 전

도저히 안되서 다시 글 남겨요..

11659번 구간 합 구하기 4 

이 문제 풀고 다시 하는데 시간초과가 나서 

loop 하나라도 줄이면 될까 싶어서 main에 주석처리 한 부분을 something() 안에 넣고 해봤는데

시간초과가 나오진 않고 틀렸습니다가 나오네요..

입력 받는것만 BufferedReader쓰고 출력은 그냥 했어요

반례가 있는걸까요 아니면 코드 자체가 틀린걸까요?

jh05013   2년 전

이러면 prefixSum이 제대로 계산되지 않습니다. prefixSum[i]만 바뀌는데 실제로는 전부 바꿔야 하기 때문입니다.

ylee399   2년 전

@jh05013

이런식으로 하면 시간초과가 나는데 시간을 줄일 방법이 있을까요?

jseo   2년 전

주어지는 jump 값이 전부 1인 경우를 생각해보세요. 총 수행시간은 O(N * numJumps) 가 될겁니다. 

하지만 굳이 jump = 1 케이스마다 something을 호출할 필요가 있을까요? 

예를 들어서 jump = 1인 입력이 k개라고 하면, something(1) 함수를 한번만 호출하고 array[i] = array[i] + k를 하면 시간을 훨씬 단축 시킬수 있겠죠.

jump = 2, 3, ... N인 입력도 마찬가지구요.

그리고 이러한 식으로만 해도 꽤 효율적이라는건 제가 전에 답변한 식으로 증명 할 수 있습니다.

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