파이썬 알고리즘 공부 - 구간 합

합 배열을 만들어 두고 이를 통해 구간 합을 구할 수 있다. 

 

구간합:

 

s[j]-s[i-1]

=> i~j까지의 구간 합

 

예제 풀이

import sys
N,M=map(int, sys.stdin.readline().split())
num=sys.stdin.readline().split()
li=[]
for i in range(M):
    new=(sys.stdin.readline().split())
    li.append(new)


sectionsurplus=[0,int(num[0])]
for i in range(0,len(num)-1):
    sectionsurplus.append(int(num[i+1])+int(sectionsurplus[i+1]))


for i in range(M):
    A=int(li[i][1])
    B=int(li[i][0])-1
    print(sectionsurplus[A]-sectionsurplus[B])

백준 116659번 문제

https://www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4

 

---

 

import sys
secSur=[]
matrix=[]
index=[]

input=sys.stdin.readline
N,M=map(int, input().split())

for i in range(N):
    inp=input().split()
    matrix.append(inp)

for i in range(M):
    inp=input().split()
    index.append(inp)

for i in range(N):
    secSur.append([0])
    for a in range(N):
        sur=int(matrix[i][a])+int(secSur[i][a])
        secSur[i].append(sur)

answer=0
for i in range(M):
    x1=int(index[i][0])
    y1=int(index[i][1])
    x2=int(index[i][2])
    y2=int(index[i][3])
    for a in range(x1-1, x2):
        answer+=int(secSur[a][y2])-int(secSur[a][y1-1])
    print(answer)
    answer=0

백준 11660번 

https://www.acmicpc.net/problem/11660

11660번: 구간 합 구하기 5

그런데 이 코드는 시간 초과로 정답이 아니다. 나는 구간합 배열을 가로 행만 생각해서 만들었기 때문에 구간합 이중 리스트를 또 for문으로 순회해야 하는 문제가 생겼다. 코드의 시간제한은 1초로 N의 범위가 최대 1024, M의 최대 범위가 100000인걸 고려하면 최대 NlogN 시간복잡도를 가진 코드 까지가 통과 가능하다. 최대 N*M의 시간 복잡도(x1==0, x2==N일 때)를 가지는 내 코드는 시간 초과라는 결과가 뜰 수밖에 없다.

 

코드의 시간 복잡도: O(N * M) = 1024 * 100000 = 102400000 즉 연산 횟수가 102400000번 이라는 것을 뜻한다. 

파이썬에서는 1초에 2000만~ 1억번 정도의 연산을 하므로 1억이 넘어가는 연산 횟수는 1초 이상의 시간이 걸리게 된다.

 

따라서 세로 행도 구간합을 만들어 이중배열에 저장하는 코드가 필요하다. 이 코드는 구간합 배열을 만들어두면 이 배열을 다시 순회할 필요 없이 인덱스로 원하는 값을 찾을 수 있기 때문이다.

이 원리를 적용해 secSur에서 원하는 사각형의 합을 구한다!

import sys
input=sys.stdin.readline
N,M= map(int, input().split())
matrix=[[0]*(N+1)] #이중 리스트. 0이 N+1개 있는 리스트 하나 만들어줌 
secSur=[[0]*(N+1) for _ in range(N+1)] #이중 리스트. 0이 N+1개 있는 리스트가 N+1개 있음 (N+1)*(N+1)

for i in range(N):
    row=[0] + [int(x) for x in input().split()] # row=[0,입력값----]
    matrix.append(row)


#secSur 구하기
for i in range(1, N+1):
    for a in range(1,N+1):
        #해당 셀까지의 구간 합= 해당 셀의 왼쪽칸 + 위쪽칸 - 대각선 왼쪽 위 칸 + 해당 셀의 값
        secSur[i][a]= secSur[i][a-1] + secSur[i-1][a] -secSur[i-1][a-1] + matrix[i][a]

for _ in range(M):
    x1,y1,x2,y2 = map(int, input().split())
    answer=secSur[x2][y2] - secSur[x1-1][y2] - secSur[x2][y1-1] + secSur[x1-1][y1-1]
    print(answer)

 

---

 

import sys
input=sys.stdin.readline
N,M=map(int, input().split())
num=input().split()

secSur=[0]
#구간 합 배열 만들기
for i in range(N):
    secSur.append(secSur[i]+int(num[i]))

#구간 합 배열 0 제거
secSur=secSur[1:]

answer1=0
#나머지 배열 만들기 ( 나머지가 0이면 0번 인덱스에 +1, 나머지가 4면 4번 인덱스에 +1)
rest=[0]*(M)

for i in range(len(secSur)):
	#만약 나머지 0이면 그 개수만큼 +
    if secSur[i]%M==0:
        answer1+=1
    #구간합 배열 '나머지'로 재구성 하기
    secSur[i]=secSur[i]%M
    #나머지 확인 후 나머지 배열의 해당 인덱스에 +1 -> 나머지가 k인 수가 몇갠지 파악
    rest[secSur[i]]+=1

#나머지 배열에서 2이상인 애들은 NC2 해주기
for i in rest:
    if i>1:
        answer1+= i*(i-1)/2

print(int(answer1))

백준 10986번

https://www.acmicpc.net/problem/10986

10986번: 나머지 합

 

나머지 문제는 유형도 여러가지이고 수학적 센스를 이용해 답을 찾는 경우가 많다. 

이 문제는 나머지가 0인 경우, 아닌 경우 나누어서 세는데,

 

1. 구간합을 구해 M으로 나누었을 때 나머지가 0인 경우의 수를 세어서 answer에 더한다.

2. 구간합 배열을 for문으로 순회하며 해당 셀들을 M으로 나눈 나머지로 업데이트한다. 이때, 나머지 배열에 해당 인덱스 값에도 +1을 해주어 나머지가 k인 셀들의 개수를 센다.

3. 나머지 배열을 순회하며 k번째 셀에 쌓인 숫자가 2 이상이면 (해당숫자 C2)를 계산해 답에 더한다.

 

A-B=3의 배수이면 (A+1)-(B+1)도 3의 배수이다!

즉 3으로 나눈 나머지가 같은 두 수는 그 차가 3의 배수이다!! 를 이용해서 풀어내면 된다.