cfghj101   5년 전

O(N)이 되려면..

예제입력처럼 1 2 3 2 1 배열이 주어진다면 첫번째 원소인 1의 경우 1 2 3 2 에서 합이 최초로 7보다 커지기 때문에,
두번째 원소인 2를 조사할 때에는 2, 2+3, 2+3+2, 2+3+2+1 이렇게 다 조사할 필요 없이
2+3+2부터 7보다 큰지 조사하도록 했습니다. 

또 1 2 3 2에서 최초로 7보다 커진다면 그 다음 구간들도 예를 들어 1 2 3 2 1도 합이 7보다 크기 때문에, 1 2 3 2의 마지막 인덱스를 j라고 했을 때 count += n - j + 1로 카운트를 증가시키도록 했습니다.

예제 입력 외에 다른 입력들을 테스트했을 땐 정답이 나오는데, 채점 시 시간초과가 아니라 틀리게 채점되어 질문을 올립니다

틀린 테스트케이스가 무엇이 있을까요?

betain24   5년 전

정답의 범위가 20억이 넘을수도있습니다..

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