[Do-it! 코딩 테스트-기초편] 004. 구간 합 구하기 2

문제

https://www.acmicpc.net/problem/11660

11660번: 구간 합 구하기 5

---

접근

2차원 합 배열을 구한다.

D[x][y] = (0, 0) 부터 (x, y) 까지의 사각형 영역 안에 있는 수의 합

부분 합은 D[x2][y2]에서 어떤 구간의 합을 빼면 구할 수 있다.

---

코드

import sys
input = sys.stdin.readline

N, M = map(int, input().split(' '))
D = [[0] * N] * N
result = [0] * M

for i in range(N):
    D[i] = list(map(int, input().split(' ')))  # [[1, 2, 3, 4], 0, 0, 0
# 1
for i in range(N):
    for j in range(N):
        if i == 0 and j == 0:
            D[i][j] = D[i][j]
        elif i == 0:
            D[i][j] = D[i][j] + D[i][j - 1]
        elif j == 0:
            D[i][j] = D[i][j] + D[i - 1][j]
        else:
            D[i][j] = D[i][j] + D[i][j - 1] + D[i - 1][j] - D[i - 1][j - 1]
# 2
for i in range(M):
    x1, y1, x2, y2 = map(int, input().split())
    x1 = x1 - 1
    y1 = y1 - 1
    x2 = x2 - 1
    y2 = y2 - 1
    if x1 == 0 and y1 == 0 and x2 == 0 and y2 == 0:
        result[i] = D[x1][y1]
    elif x1 == 0 and y1 == 0:
        result[i] = D[x2][y2]
    elif x1 == 0:
        result[i] = D[x2][y2] - (D[x2][y1 - 1])
    elif y1 == 0:
        result[i] = D[x2][y2] - (D[x1 - 1][y2])
    else:
        result[i] = D[x2][y2] - (D[x1 - 1][y2] + D[x2][y1 - 1] - D[x1 - 1][y1 - 1])

for i in result:
    print(i)

---

설명

불필요하게 가독성을 떨어뜨리는 부분이 있는 것 같다. 하지만 차근차근 보면 직관적으로 이해하기 쉽게 짰다고 생각한다..

 

# 1 합 배열을 구하는 부분.

(i, j),  2차원 배열을 NxN으로 나타냈을 때의 해석

(0, 0) -> 자기 자신

(0, j) -> 왼쪽 1열로 (i - 1) 인덱스가 없기 때문에 자기 자신에 (j - 1) 값만 더해준다.

(i, 0) -> 위쪽 1행으로 (j - 1) 인덱스가 없기 때문에 자기 자신에 (i - 1) 값만 더해준다.

그 외 (i, j) -> D[i][j] = D[i][j] + D[i][j - 1] + D[i - 1][j] - D[i - 1][j - 1]

자기 자신과 왼, 위, 왼쪽 위 대각선을 모두 더한 값이다.

 

각 구역을 위의 연산 값으로 변경하면 합 배열이 완성된다.

 

구한 합배열을 사용해서 부분 합을 쉽게 구할 수 있다.

 

# 2 부분 합을 구하는 부분

부분의 시작 좌표와 끝 좌표를 입력받는다.

문제에서는 입력 인덱스를 0, 0 부터가 아닌 1, 1 ~ 4, 4 로 보고 있기 때문에 각 입력 좌표에 -1을 해준다.

 

합 배열 구할때와 마찬가지로 0, 0 이나 0번 인덱스가 포함된 부분의 연산을 조건문을 주어 따로 해결했다.

 

구하고자 하는 부분 합이 다음과 같다고 하면

x2, y2 부분 합을 구한다. 예시의 부분 합은 42이다.

위의 부분 합에서 빼야할 부분은 다음과 같다. 42 - (6 + 10)

위 두 부분을 빼면 겹치는 부분이 두 번 빼지기 때문에 겹치는 부분을 더해준다. 42 - (6 + 10) + 1

위 예시대로 공식을 만들면 

result[i] = D[x2][y2] - (D[x1 - 1][y2] + D[x2][y1 - 1] - D[x1 - 1][y1 - 1])

---

피드백

책의 해답에는 아래와 같이 배열의 크기를 늘려서 인덱싱문제를 해결한 것 같다.

나의 답처럼 인덱싱을 고려한 조건을 주지 않아도 되기 때문에 더 간결한 코드로 문제를 해결할 수 있다.

---

알고리즘

2023.10.21 - [파이썬/알고리즘] - [알고리즘] 구간 합

[알고리즘] 구간 합