백준 / 구간 합 구하기 5 / 11660번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 구간 합 구하기 5 / 11660번 (실버 1단계)

문제 사이트: https://www.acmicpc.net/problem/11660

 

문제 설명

---

나의 풀이

import sys
input = sys.stdin.read

def main():
    data = input().split()
    idx = 0

    n = int(data[idx])
    idx += 1
    m = int(data[idx])
    idx += 1

    chart = [[0] * (n + 1) for _ in range(n + 1)]
    prefix = [[0] * (n + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for j in range(1, n + 1):
            chart[i][j] = int(data[idx])
            idx += 1
            prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + chart[i][j]

    output = []
    for _ in range(m):
        x1 = int(data[idx])
        idx += 1
        y1 = int(data[idx])
        idx += 1
        x2 = int(data[idx])
        idx += 1
        y2 = int(data[idx])
        idx += 1

        result = prefix[x2][y2] - prefix[x1-1][y2] - prefix[x2][y1-1] + prefix[x1-1][y1-1]
        output.append(str(result))

    print('\n'.join(output))

main()

---

※ 알아야 할 것

이번 문제는 누적합을 이용한 풀이를 사용하셔야합니다. for 반복문을 이용하여 문제를 해결하는 경우 시간 초과가 발생할 수 있습니다!