목록부분합 (1)
haju__log
[python][백준/BOJ] 11659번 : 구간 합 구하기 4 - 누적합, 부분합
https://www.acmicpc.net/problem/11659 ✅ 시간초과 난 코드import sysn,m =map(int,sys.stdin.readline().split())l=list(map(int,sys.stdin.readline().split()))print(l)for k in range(m): i,j =map(int,sys.stdin.readline().split()) sum =0 for q in range(i-1,j): sum+=l[q] print(sum)N,M의 범위가 최대 100,000 이고, i,j 범위를 최대로 했을 경우, 시간복잡도의 최대는 O(N^2) 이기에 시간초과남 ✅ 누적합(Prefix Sum)배열에서 특정 구간의 합을 빠르게 구할 수 있..
BOJ_백준
2025. 3. 19. 14:36