[BOJ] 백준 11660 구간 합 구하기 5 (Swift)

문제

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

11660번: 구간 합 구하기 5

풀이

2차원 배열의 구간 합을 구하는 문제입니다.

구간 합을 한 번 구해볼까요?

다음 수는 1 + 2 + 2 + 3 으로 8을 채워줘야 합니다.

채울 수의 위, 왼쪽을 보면 3으로 구간합이 이미 채워져 있습니다.
이 두 수의 3은 1 + 2, 1 + 2 로 채워져 있는데, 1이 중복되고 있습니다.
따라서 중복된 1을 빼주어야 합니다.
3 + 3 - 1 + 3(자신의 수) 로 구간 합을 구할 수 있습니다.

그렇다면 구간 합을 구하는 식은
$table(y, x) = table(y, x) + table(y - 1, x) + table(y, x - 1) - table(y - 1, x - 1)$로 구할 수 있습니다.

그렇다면 (y1, x1) 부터 (y2, x2)의 합은 어떻게 구할 수 있을까요?

(2, 2)에서 (3, 4) 까지의 합을 구하는 경우를 살펴보겠습니다.

먼저, (1, 1)에서 (3, 4) 까지의 합은 다음과 같습니다.

(1, 1) 부터 (1, 4)의 합(10)을 빼주면 (2, 1) 에서 (3, 4) 까지의 합을 구할 수 있습니다.

(1, 1) 부터 (2, 1)의 합(6)을 뺴주면 (2, 2) 에서 (3, 4) 까지의 합을 구할 수 있습니다.

그런데, (1, 1)을 2번씩이나 빼주었네요.. 이 값(1)을 더해줍시다.

따라서 답은 42 - 10 - 6 + 1 = 27이 나오게 됩니다.

이것을 식으로 작성하면
$table(y2,x2) - table(y1 - 1,x2) - table(y2,x1 - 1) + table(y1 - 1,x1 - 1)$ 으로 나타낼 수 있습니다.

소스코드

후기

2차원 배열의 구간 합을 구하는 문제였습니다.
직접 표를 채워보면서 이해하는데 도움이 되었습니다.