# 데이터 인풋 import sys input = sys.stdin.readline n, m = map(int, input().split()) arr = [] for i in range(n): arr.append(list(map(int, input().split()))) # 각 셀을 기준으로 누적합 dp = [[0] * (n + 1) for i in range(n + 1)] for i in range(1, n + 1): for j in range(1, n + 1): dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1] + arr[i - 1][j - 1] # 범위 지정하여 구하기 for k in range(m): x1, y1, x2, y2 = map(int..

문제링크 https://programmers.co.kr/learn/courses/30/lessons/92344 무지성으로 풀면 무조건 시간초과난다 이 문제는 정확성과 효율성이 따로 구분되어있다. 무조건 모든 방식에서 생각해봐야한다는거다 시간초과 코드는 하단에 첨부한다 사전지식 : 누적합 보통 구간의 합계를 sum(리스트시작:리스트끝) 이걸로 구하는데 이게 리스트길이만큼의 시간복잡도가 사용된다. 그러면 합산 한번당 O(n)이 걸리는데 당연히 연산 횟수가 많아지면 많아질수록 비례해서 길어질것이다 그런데 누적합을 사용한 방식은 누적합계를 더한다음에 리스트끝원소-리스트시작원소 를 지정해서 계산하는데 리스트인덱싱1개는 O(1)이거든요. 그래서 누적합은 O(1)+O(1) 시간에 구간의 합계를 구할수 있어서 사용한다..