시작 👊

구간 합 구하기 2!

👨‍💻 문제

백준 11660

질의의 개수가 100,000이므로 이 문제 역시 질의마다 합을 구하면 안되고, 구간 합 배열을 이용해야 한다.
구간 합 배열이 1차원에서 2차원으로 확장된 것으로 생각하여 구간 합 배열을 어떻게 구성할지 고민하는 것이 이문제의 핵심입니다.

정말 댕청한 나는 어떻게 해야할지 정말 하나도 감이 안 잡힌다.

2차 구간 합 배열 D[X][Y] 정의

D [ X ][ Y ] = 원본 배열의 (0, 0)부터 (X, Y)까지의 사각형 영역 안에 있는 수의 합

1 구간 계산

✅ D[1][j] = D[1][j-1] + A[1][j]

✅ D[i][1] = D[i-1][1] + A[i][1]

나중에 이 구간을 매우 많이 사용할 것이다.

이를 통해

나머지 2차원 구간 합 배열을 채웁니다.

✅ D[i][j] = D[i][j-1] + D[i-1][j] - D[i-1][j-1] + A[i][j]

아휴...
너무 어렵습니다 선생님...

그래서

$X_1 ,Y_1 ,X_2 ,Y_2$에 대한 답을 구간 합으로 구하는 식

✅ D[X2][Y2] - D[X1-1][Y2] - D[X2][Y1-1] + D[X1-1][Y1-1]

아무튼 이렇다..

입력 받으려면 한 줄씩 입력 받아서 split 으로 나눠 변수에 넣어주고 그걸 사용해야하므로,

sudo 코드를 짜보면

import sys
input = sys.stdin.readline

# N 은 2차원 배열의 크기, M 은 반복되는 질문의 수
N, M = map(input().split())


# 위에서 N 번 만큼 for 문으로 값을 배열에 넣어주자.
for i in range(N):
	# 아 데이터를 넣을 변수가 필요하네
	데이터 numList 에 넣자
    
# 그다음 어떻게 하지...?
#저 식을 그대로 써보자
for i in range(N):
	for j in range(M):
    	sumList[i][j] = sumList[i][j-1] + sumList[i-1][j] - sumList[i-1][j-1] + A[i][j]

# 그 다음 이제 numList 도 이쏙 sumList도 있으니 바로 계산하면 될듯.
for i in range(M):
	x1, y1, x2, y2 = map(input().split())
    # 이렇게 하면 좌표는 다 넣을 수 있고,
    result = D[x2][y2] -D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1-1]
    print(result)
   

어휴 대가리 깨지겠네.

진짜 하나도 못 하겠다.
풀이보고 대충 해봐야지

import sys
input = sys.stdin.readline

N, M = map(int, input().split())

numList = [[0] * (N+1)]
sumList = [[0] * (N+1) for _ in range(N+1)]

for i in range(N):
    numList_row = [0] + [int(x) for x in input().split()]
    numList.append(numList_row)

for i in range(1, N+1):
    for j in range(1, N+1):
        sumList[i][j] = sumList[i][j-1] + sumList[i-1][j] - sumList[i-1][j-1] + numList[i][j]

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

아 강의를 볼 때는 이해가 되는데,
내가 다시 풀라고 하면 전혀 못 하겠네..

세번 더 봐야겠다...😔

난 아직 댕청이다

---

저자 강의