[백준] 11660번 : 구간 합 구하기 5 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

11660번: 구간 합 구하기 5

 

1. 문제 설명

2. 풀이과정

질의의 개수가 100,000이므로 해당 문제는 질의마다 합을 구하면 안 되고, 구간 합 배열을 이용해야 한다.

표가 2차원이므로 구간 합 배열 또한 2차원 배열로 생성해야 한다.

해당 구간 합 배열을 어떻게 구성할 것인지 고민하는 것이 문제의 핵심이다.

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

 

1. 2차원 구간 합 배열의 1행, 1열부터 구한다.
2. 구간 합 배열 1행 : S[i][j] = S[i][j - 1] + A[i][j]
3. 구간 합 배열 1열 : S[i][1] = S[i - 1][1] + A[i][1]
4. 위 식을 통해 나머지 2차원 구간 합 배열을 채운다. S[i][j] = S[i][j - 1] + S[i - 1][j] - S[i - 1][j - 1] + A[i][j]
5. 예를 들어 질의 가 2 2 3 4라면 (3, 4) 구간 합에서 (1, 4) 구간 합, (3, 1) 구간 합을 뺀 다음 중복하여 뺀 (1, 1) 구간 합을 더한다.

슈도코드

1. N(리스트 크기), M(질의 수)
2. A(원본 리스트)
3. S(구간 합 배열)
4. for n만큼 반복 : 원본 리스트 데이터 저장
5. for i를 1부터 N까지 반복
6. for j를 1부터 N까지 반복
7. 합 배열 저장 S[i][j] = S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1] + A[i][j]
8. for M만큼 반복
9. startR, startC, endR, endC
10. 질의에 대한 결과 계산 S[endR][endC] - S[startR - 1][endC] - S[endR][startC - 1] + S[startR - 1][startC - 1]

반응형

3. 소스코드

import sys

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

A = [[0] * (N + 1)]
for _ in range(N):
    li = [0] + [int(x) for x in sys.stdin.readline().split()]
    A.append(li)
    
S = [[0] * (N + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
    for j in range(1, N + 1):
        S[i][j] = S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1] + A[i][j]
        
for _ in range(M):
    startR, startC, endR, endC = map(int, sys.stdin.readline().split())
    result = S[endR][endC] - S[startR - 1][endC] - S[endR][startC - 1] + S[startR - 1][startC - 1]
    print(result)