문제 설명
•
수 개가 주어졌을 때, 번째 수부터 번째 수까지 합을 구하는 문제
예제 입력/출력
•
입력1
4 3
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7
2 2 3 4
3 4 3 4
1 1 4 4
Plain Text
복사
•
출력1
27
6
64
Plain Text
복사
제약 조건
•
•
◦
◦
문제 풀이
풀이1 브루트 포스 -
풀이2 그리디
풀이3 DP -
풀이 코드
import sys
input = lambda: sys.stdin.readline()
# 입력 값 받기
N, M = map(int, input().split())
matrix = [[0] * (N + 1)]
for _ in range(N):
matrix.append([0] + list(map(int, input().split())))
# 누적 합 행렬 생성
psum = [[0] * (N + 1) for _ in range(N + 1)]
for y in range(1, N + 1):
for x in range(1, N + 1):
psum[y][x] = (psum[y - 1][x] + psum[y][x - 1] - psum[y - 1][x - 1]) + matrix[y][x]
# 합 연산 수행
for _ in range(M):
y1, x1, y2, x2 = map(int, input().split())
total = psum[y2][x2] - (psum[y2][x1 - 1] + psum[y1 - 1][x2] - psum[y1 - 1][x1 - 1])
print(total)
Python
복사
