[구현/수학] 백준 11660 구간 합 구하기 5 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

11660번: 구간 합 구하기 5

 

 

 

2. 문제 풀이

 2차원 행렬의 구간 합을 구하는 문제입니다.

 

2022.02.14 - [Algorithm] - [구현/수학] 백준 11659 구간 합 구하기 4 - Python

[구현/수학] 백준 11659 구간 합 구하기 4 - Python

 매번 구간 합을 구할 때마다 2중 for문을 사용하면 시간 초과가 납니다. 그 대신 '누적 합' 개념을 사용해야 합니다. 위 링크에서 누적 합 개념과 코드를 설명했으니, 참조해주시기 바랍니다. 

 

 

 

3. 코드

import sys
input = sys.stdin.readline

# 입력
N, M = map(int, input().split())
sumlist = []  # 누적 합
for _ in range(N):
    row = list(map(int, input().split()))
    tmp = []
    _sum = 0
    for num in row:
        _sum += num
        tmp.append(_sum)
    sumlist.append(tmp)

# 출력
for _ in range(M):
    x1, y1, x2, y2 = map(int, input().split())
    res = 0
    for i in range(x2-x1+1):
        if y1-2 == -1:
            res += sumlist[x1+i-1][y2-1]
        else:
            res += sumlist[x1+i-1][y2-1] - sumlist[x1+i-1][y1-2]
    print(res)

 구간 합 구하기 4 문제와 달리, 구간 합 구하기 5는 '2자원 행렬'의 구간 합을 구해야 합니다. 어렵게 생각할 필요 없이, 행마다 누적 합을 계산해서 구해주면 됩니다.

 주의할 점은 y1-2가 -1이 되면 맨 앞이 아니라 맨 끝을 참조하게 되므로, 따로 예외처리를 해줘야 합니다.