백준(11659,11660)

백준(구간합)

구간 합 1차원(11659)

• 입출력 예시 :

5 3
5 4 3 2 1
1 3
2 4
5 5
-------------------------------
12
9
1

해결책

1. 누적합 배열 생성

S[n]=S[n-1]+A[n]

1. A[i]+…A[j] = S[j]-S[i-1]

코드

a,b=map(int,input().split())
numbers=list(map(int,input().split()))
sum=[0]*a
sum[0]=numbers[0]
result=[]
for i in range(1,a):
    sum[i]=sum[i-1]+numbers[i]

for i in range(b):
    s,e=map(int,input().split())
    if s==1 :
        result.append(sum[e-1])
    else :
        result.append(sum[e-1]-sum[s-2])

for i in result:
    print(i)

구간 합 2차원(11660)

• 입출력 예시 :

4 3
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7
2 2 3 4
3 4 3 4
1 1 4 4
----------------------
27
6
64

해결책

1. 누적합 배열 생성

   1차원과 달리 2차원에서는 i,j 좌표값에서 [i-1,j] + [i,j-1] 하고 중복되는 [i-1][j-1]을 빼주면서 생성해준다.

2. 시작점을 x1,y1 도착점을 x2,y2라고 하였을때,

   D[x2][y2]는 D[x1][y1]뿐만이 아니라 x1이전값과 y1이전값들의 누적합을 포함하고 있는 값이기에, D[x2][y2]-D[x1-1][y2]-D[x2][y1-1]하고 +D[x1-1][y1-1]을 계산해준다.

   ### 코드

    n, m = map(int, input().split())
    A=[[0]*(n+1)]
    D=[[0]*(n+1) for _ in range(n+1)]
    result=[]
    for i in range(n):
        tmp = [0]+[int(x) for x in input().split()]
        A.append(tmp)
       
    for i in range(1,n+1):
        for j in range(1,n+1):
            D[i][j]=D[i-1][j]+D[i][j-1]-D[i-1][j-1]+A[i][j]
       
    for k in range(m):
        x1,y1,x2,y2 = map(int,input().split())
        result.append(D[x2][y2]-D[x1-1][y2]-D[x2][y1-1]+D[x1-1][y1-1])
       
    for i in result:
        print(i)