자료구조-구간합

이론

📖 구간 합?
합 배열을 이용하여 시간복잡도를 더 줄이기 위해 사용하는 특수 목적의 알고리즘.

📖 합 배열 S 정의

• S[i]=A[0]+A[1]+A[2]+ ... + A[i-1]+A[i]

미리 합 배열을 정의하여 문제풀이에 이용하면, 기존 리스트의 일정범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소하므로 좀 더 효율적으로 코드를 작성할 수 있다.

📖 합 배열 S 를 이용한 공식들

• S[i]=S[i-1]+A[i]
• i에서 j까지의 구간 합 : S[j]-S[i-1]
• 2차원 배열의 구간 합 : S[i][j]=S[i][j-1]+S[i-1][j]-S[i-1][j-1]+A[i][j]

문제풀이

📖 백준 11660

#2차원 배열 구간합
#S[i][j]=S[i][j-1]+S[i-1][j]-S[i-1][j-1]+A[i][j]
#(x1,y1)~(x2,y2)의 합: S[x2][y2]-S[x1-1][y2]-S[x2][y1-1]+S[x1-1][y1-1]

import sys
input=sys.stdin.readline

n,m=map(int,input().split())
A=[[0]*(n+1)]
S=[]

for i in range(n):
	row=[0]+[int(x) for x in input().split()]
	A.append(row)

for i in range(n+1):
	s=[0]*(n+1)
	S.append(s)

for i in range(1,n+1):
	for j in range(1,n+1):
		S[i][j]=S[i][j-1]+S[i-1][j]-S[i-1][j-1]+A[i][j]

for i in range(m):
	x1,y1,x2,y2=map(int,input().split())
	result=S[x2][y2]-S[x1-1][y2]-S[x2][y1-1]+S[x1-1][y1-1]
	print(result)

📖 백준 10986

✏ (A+B)%C 는 ((A%C)+(B%C))%C 와 같다.
특정 구간 수들의 나머지 연산을 더해 나머지 연산을 한 값과 이 구간의 합의 나머지 연산을 한 값은 같다.

✏ S[i]%M 과 S[j]%M 이 같다면, (S[j]-S[i])%M은 0이다.
따라서, 구간 합 배열의 원소를 M으로 나눈 나머지로 업데이트 하고

1) 원소값이 0 (나머지값이 0)인 개수를 센다.
2) 원소값이 같은(나머지값이 같은) 인덱스의 개수를 센다. 인덱스의 개수가 n개라면 nC2를 이용하여 경우의 수를 구한다.
3) 1)의 값과 2)의값을 더한다.

# (A+B)%C = ((A%C)+(B%C))%C 
# S[i]%M 과 S[j]%M 이 같다면, (S[j]-S[i])%M은 0이다.
# 나머지의 개수가 같은 값의 개수를 세어 조합을 이용하여 경우의수를 구한다.

import sys
input=sys.stdin.readline

n,m=map(int,input().split())
test=list(map(int,input().split()))
tmp=0
sum=[]
c=[0]*m
result=0

for i in test:
	tmp+=i
	sum.append(tmp)

for i in range(n):
	mod=sum[i]%m
	if (mod==0):
		result+=1
	c[mod]+=1

for i in range(m):
	if(c[i]>1):
		result+=(c[i]*(c[i]-1)//2)

print(result)	

◼ 참고사항

• DO it! 알고리즘 코딩테스트
• 백준