-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
섹션 3 수들의 합 문제 제 풀이 어디가 문제인지 한 번만 봐주십쇼
23.07.04 00:53 작성 조회수 248
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)
답변을 작성해보세요.
1
김태원
지식공유자2023.07.05
안녕하세요^^
안쪽 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
khjj9865
2023.07.04
a[i]...a[i+2] 도 정답 count될 수 있지만 a[i-2]...a[i] 도 count될 수 있어서 1개의 답이 2번 count될 수 있는 코드네요
답변 3