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

이차원 배열의 구간합 구하는 법을 고민하게 해준 문제이다.

문제의 핵심은 다음과 같이 나뉜다.

• 입력 받은 값들을 누적합으로 만들기
• 누적합으로 만든 배열 이용해 (x2,y2),(y1,x1) 까지의 합 구하기

입력 받은 값을 누적합으로 만들려면 리스트 패딩을 이용하면 쉽게 된다.
구현 팁은 아래 링크를 참고 하면 된다.
https://velog.io/@greten/python-List-padding

(x2,y2),(y1,x1) 까지의 합은 아래 그림을 고민 해 보면 알 수 있다.

초록 네모의 넓이를 구하기 위해선

검정 네모 - 파랑 네모 + 노랑 네모를 하면 된다.

이를 파이썬 코드로 짜면 다음과 같다.

N, M = map(int, input().split())  # N 배열의 크기, M 연산 횟수
arr = [[0]*(N+1)] + [[0] + list(map(int, input().split())) for _ in range(N)]  # 배열의 크기 + 1 만큼 생성, 0은 패딩
prefix = [[0 for _ in range(N+1)] for _ in range(N+1)]  # 누적합
for i in range(1, N+1):  # 2차원 배열 누적합
    for j in range(1, N+1):
        prefix[i][j] = prefix[i][j-1] + prefix[i-1][j] + arr[i][j] - prefix[i-1][j-1]

for _ in range(M):  # 연산 횟수 만큼 반복
    x1, y1, x2, y2 = map(int, input().split())
    print(prefix[x2][y2]+prefix[x1-1][y1-1]-prefix[x1-1][y2]-prefix[x2][y1-1])

파이썬은 sys.stdin.readline을 생활화 해야한다.