[백준 11660번] 구간 합 구하기 5

인증사진(2024-06-23)

 

문제

N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.

예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.

1	2	3	4
2	3	4	5
3	4	5	6
4	5	6	7

여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.

표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.

 

질의 개수가 큰 경우 ( 1 ≤ M ≤ 100,000 ) : 정답판 만들어 놓고 질의 오면 바로 답을 출력하는 형태

- 시간 복잡도 고려

 

Pcode

n : 리스트크기

m : 질의 수

D : 합배열

A : 원본리스트

 

for n만큼 반복:

 원본리스트 데이터 저장

 

for i를 1부터 n까지 반복:

 for j를 1부터 n까지 반복

  합배열 저장

  d(x2, y2) - d(x1-1,y2) - d(x2, y1-1) + d(x1-1, y1-1) + a(x,y)

 

for m 만큼 반복:

 결과 = d(x2, y2) - d(x1-1,y2) - d(x2, y1-1) + d(x1-1, y1-1) 

 

답

import sys
input = sys.stdin.readline

n , m = map(int, input().split())
A = [[0] * (n + 1)]  # 0으로 초기화된 첫 행 추가
D = [[0] * (n + 1) for _ in range(n + 1)]  # 누적합 배열 초기화

for i in range(n):
    A_row = [0] + [int(x) for x in input().split()]  # 0으로 시작하는 각 행 추가
    A.append(A_row)

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

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

 

추가공부

 

2차원 배열을 알아야 한다.

D[x][y] (0,0) 부터 (x,y) 까지 사각형 수의 합

(2,2) 구하려면 d(2,1) + d(1,2) - d(1,) + a(2,2)

 

d(x2, y2) - d(x1-1,y2) - d(x2, y1-1) + d(x1-1, y1-1)