인프런 커뮤니티 질문&답변

작성자 없음

작성자 정보가 삭제된 글입니다.

파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)

5. 수의 합

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

작성

·

185

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)으로 짜야 합니다.

작성자 없음

작성자 정보가 삭제된 글입니다.

질문하기