[BOJ][⚪1][백준#11660] 구간 합 구하기 5

문제 출처

BAEKJOON Online Judge #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이다. 표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.

입력

첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2 가 주어지며, (x1, y1)부터 (x2, y2)의 합을 구해 출력해야 한다. 표에 채워져 있는 수는 1,000보다 작거나 같은 자연수이다. (x1 ≤ x2, y1 ≤ y2)

출력

총 M줄에 걸쳐 (x1, y1)부터 (x2, y2)까지 합을 구해 출력한다.

예제

예제 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

출력

27
6
64

예제 2

입력

2 4
1 2
3 4
1 1 1 1
1 2 1 2
2 1 2 1
2 2 2 2

출력

1
2
3
4

My Sol A : 재귀 사용

import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline

def S(i, j):
    if not memo[i][j]:
        memo[i][j] = mat[i][j]
        if not i:
            memo[i][j] += S(i, j-1)
        elif not j:
            memo[i][j] += S(i-1, j)
        else:
            memo[i][j] += S(i-1, j) + S(i, j-1) - S(i-1, j-1)

    return memo[i][j]

N, M = map(int, input().split())
mat = [list(map(int, input().split())) for _ in range(N)]
memo = [[0]*N for _ in range(N)]
memo[0][0] = mat[0][0]

for _ in range(M):
    i1, j1, i2, j2 = map(lambda x: (int(x)-1), input().split())
    S1 = S(i2, j2)
    S2 = S(i1-1, j2) if i1 else 0
    S3 = S(i2, j1-1) if j1 else 0
    S4 = S(i1-1, j1-1) if (i1 and j1) else 0
    print(S1 - S2 - S3 + S4)

DP를 이용하는 문제였다. 각 좌표가 시작점부터 좌표까지의 영역의 합이고, 이를 조작해 x1, y1, x2, y2의 좌표를 이용해 계산하면 되는 문제였다.

My Sol B : while 반복문 사용

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
mat = [list(map(int, input().split())) for _ in range(N)]
S = [[0]*N for _ in range(N)]
S[0][0] = mat[0][0]

# S 채우기
# 첫 줄 채우기
j = 1
while j < N:
    S[0][j] = S[0][j-1] + mat[0][j]
    j += 1

i = 1
while i < N:
    S[i][0] = S[i-1][0] + mat[i][0]
    i += 1

# 전체 채우기
i = 1
while i < N:
    j = 1
    jsum = mat[i][0]
    while j < N:
        jsum += mat[i][j]
        S[i][j] = S[i-1][j] + jsum
        j += 1
    i += 1

for _ in range(M):
    i1, j1, i2, j2 = map(lambda x: (int(x)-1), input().split())
    S1 = S[i2][j2]
    S2 = S[i1-1][j2] if i1 else 0
    S3 = S[i2][j1-1] if j1 else 0
    S4 = S[i1-1][j1-1] if (i1 and j1) else 0
    print(S1 - S2 - S3 + S4)

재귀를 사용하는 것은 1028ms의 연산 시간과 50만 KB의 메모리가 필요했다. 그런데 반복문을 사용하면 if문이나 더하기가 훨씬 좋을 것 같아서 반복문으로도 풀어보았다. 이 풀이는 13만 KB의 메모리와 408ms의 연산 시간을 기록했다.

이는 반복문을 활용하여 조건문의 수를 획기적으로 줄였을 뿐 아니라 함수 호출을 사용하지 않는 방식이기 때문에 여러모로 효과적이었던 것 같다.

결과

맞았습니다!!