오늘의 문제 boj-11660

문제

N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.

예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.

1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7
여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.

표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.

풀이

주어진 예시를 통해 간단하게 설명해보려고 한다.

2,2 부터 3,4까지의 값을 구하려면

1 2 3 4
2 3 4 5
3 4 5 6

가로 세로 모두를 더한 누적값인 42에서 인덱스 0의 모든 칼럼 1 2 3 4 의 합을 걷어내고 0번째 칼럼의 모든 인덱스의 합을 빼주면된다.

따라서 42 - 6 - 10을 해주고 두개의 겹치는 값 1을 더해주면
27이라는 수를 얻을 수 있다.

import sys
input = sys.stdin.readline

N, M = map(int, input().rstrip().split())
matrix = [[0]* (N+1)] + [[0] + list(map(int, input().rstrip().split())) for _ in range(N)]


for i in range(1, N+1):
    for j in range(1, N):
        matrix[i][j+1] += matrix[i][j]
        

for j in range(1, N+1):
    for i in range(1, N):
        matrix[i+1][j] += matrix[i][j]

            
for _ in range(M):
    x1, y1, x2, y2 = map(int, input().rstrip().split())
    
    print(matrix[x2][y2] - (matrix[x1 -1][y2] + matrix[x2][y1-1] - matrix[x1-1][y1-1]))

피드백

모든 열과 행의 누적합을 구했다가 시간초과가 나고 각 행별 누적합을 구해 더하는 식으로 만들어서 시간초과가 났었다.

결국 힌트를 보고 나름대로 구현은 했지만 제대로 풀었다고 보기 어렵다.

이해한 바를 적어놓긴 했지만 오히려 내 부족함만 더 드러내는 것 같아 부끄럽지만 오히려 이렇게 드러내면서 배우리라 생각한다.