• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

시간 초과가 나오는 이유를 모르겠어요 ㅠㅠ

22.09.06 13:57 작성 조회수 137

0

n, m = map(int, input().split())
a = list(map(int, input().split()))

cnt = 0
for lt in range(n):
    rt = lt + 1
    tot = 0
    while tot < m and rt <= n:
        tot = sum(a[lt:rt])
        if tot == m:
            cnt += 1
            break
        rt += 1

print(cnt)

4, 5번 테스트 케이스에서 시간초과가 나옵니다 ㅜ

답변 1

답변을 작성해보세요.

0

안녕하세요^^

위에 코드는 시간복잡도가 O(n^2) 입니다. 영상처럼 O(n)으로 짜야 합니다.