(BOJ)-11660, Python

문제 요약

출처: (BOJ)11660 - 구간 합 구하기 5

$N*N$ 정방행렬이 주어졌을 때, $x_1, y_1$에서 $x_2, y_2$까지 생기는 영역에 포함되는 원소들의 합을 구하는 것이 목적이다.

• N: 정방 행렬의 크기
• M: 요구하는 영역의 수
• 행렬이 주어지고, 그 다음 줄부터 $x_1, y_1, x_2, y_2$가 M만큼 주어진다.

접근 과정

1. 완전탐색 접근

주어진 좌표에 따라 해당 영역에 속하는 원소의 합만 구하면 되겠다고 생각하고 짰다. 하지만 시간 초과라는 문구만 나왔다..

코드 구현

import sys
input = sys.stdin.readline

A, B = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(A)]
xy_list = [list(map(int, input().split())) for _ in range(B)]

for point in xy_list:
    x1, y1, x2, y2 = point
    sum = 0
    for x in range(x1-1, x2):
        for y in range(y1-1, y2):
            sum += graph[x][y]        
    print(sum)

2. 누적합 접근

이전 포스트에서 다룬 것처럼, 위의 완전탐색적 접근은 직관적이지만, 영역의 부분합을 매번 계산하므로 비효율적인 문제가 있다. 마찬가지로 누적합을 이용해서 코드를 재구성하였다!

코드 구현

A, B = map(int, input().split())

graph = [list(map(int, input().split())) for _ in range(A)]
xy_list = [list(map(int, input().split())) for _ in range(B)]
prefix = [[0 for _ in range(A+1)] for _ in range(A+1)]

for x in range(1, A+1):
    for y in range(1, A+1):
        prefix[x][y] = prefix[x][y-1] + prefix[x-1][y] - prefix[x-1][y-1] + graph[x-1][y-1]

for point in xy_list:
    x1, y1, x2, y2 = point
    answer = prefix[x2][y2] - prefix[x1-1][y2] - prefix[x2][y1-1] + prefix[x1-1][y1-1]
    print(answer)

회고

문제에서 주어진 입력만 놓고 보면, 완전탐색적 접근도 큰 무리는 없어 보인다. 하지만 행렬이 상당히 커질 경우, 영역에 포함된 원소들 전부를 다시 계산하다 보니 당연하게도 시간초과라는 문제가 발생할 수밖에 없다. 언제든 문제를 풀 때, 완전탐색적 사고를 기본으로 하되, 극단적인 상황까지 고려하며 누적합과 같은 효율적인 알고리즘을 쉽게 떠올리기 위해 노력해야겠다.