인프런 커뮤니티 질문&답변
작성한 질문수
섹션 3 수들의 합 문제 제 풀이 어디가 문제인지 한 번만 봐주십쇼
작성
·
325
0
강사님의 풀이랑은 많이 다르지만 논리적으로 문제를 못 찾겠는데, 채점시 틀리는 케이스가 있고, 런타임 오류도 생깁니다. 도움 부탁드립니다.
import sys
sys.stdin=open("C:/Users/Desktop/AA/섹션 3/5. 수들의 합/in1.txt", 'r')
n,m = map(int,input().split())
lst = list(map(int,input().split()))
cnt = 0
for i in range(0,len(lst)):
for j in range(1,len(lst)):
if sum(lst[i:j]) == m:
cnt +=1
print(cnt)답변 3
1
김태원
지식공유자
안녕하세요^^
안쪽 j for문을 약간 수정해야 합니다. 그리고 이 방법은 시간복잡도가 O(n^2)인 코드입니다. 아마 타임리밋이 날겁니다. 아래는 수정한 코드입니다.
n,m = map(int,input().split())
lst = list(map(int,input().split()))
cnt = 0
for i in range(0,len(lst)):
for j in range(i+1,len(lst)+1):
if sum(lst[i:j]) == m:
cnt +=1
print(cnt)요즘은 이 문제를 영상처럼 하지 않고 아래와 같이 코드를 짜고 있습니다. 시간복잡도는 O(n)입니다. 한 번 분석해보세요.
n, m = map(int,input().split())
lst = list(map(int,input().split()))
lt = sumN = cnt = 0
for rt in range(len(lst)):
sumN += lst[rt]
while sumN > m:
sumN -= lst[lt]
lt += 1
if sumN == m:
cnt += 1
print(cnt)1
1
안녕하세요^^ khjj9865님
좋은 답변을 해주셔서 감사합니다.