[C++] 백준 11660번 구간 합 구하기 5

다이나믹 프로그래밍 문제의 한 분야인 누적 합 문제.

처음에는 어떤 문제인지 몰라서 헤맸는데,

검색해서 이렇게 푸는 문제구나 라고 알게된 후 풀었다.

누적 합이라는 알고리즘을 사용해서 푸는 대표적인 문제였다.

 

문제풀이

문제에서 입력하는 (x1, y1)과 (x2, y2)를 입력받으면, 구간의 사이즈가 정해진다.

문제의 예시인 (2, 2)부터 (3, 4)까지라면

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

위에 파란색 배경에 흰색 글자로 된 숫자들이 구간으로 된다.

즉, x1이 행의 시작, y1이 열의 시작이 되고

x2가 행의 끝 y2가 행의 끝이 된다.

 

따라서 우리는 입력을 받을 때, 누적 합의 정보를 배열로 저장해놔야 한다.

어떻게 저장할 수 있을까?

 

누적 합 저장하기

나 같은 경우에는 위처럼 생각하고 문제를 풀었다.

저장해놓는 모든 누적합은 (1, 1)부터 시작하게 된다. (x, y)의 좌표순서라고 할 때,

(1, 1)에서 (2, 2)까지 예시를 들어보자.

1	2	3
2	3	4
3	4	5

위와 같이 입력을 받았을 때 누적합을 입력받는 배열을 순차적으로 그려보겠다.

그냥 원소의 값은 arr(x, y)라 하고, 누적합을 입력받는 배열의 값은 dp(x, y)라 하겠다.

1	0	0
0	0	0
0	0	0

1. 맨 처음 dp(1, 1)의 값은 최초의 값이므로 arr(1, 1)이다.

1	3	0
0	0	0
0	0	0

2. dp(1, 2)의 값은 dp(1, 1) + arr(1, 2)이다.

1	3	6
0	0	0
0	0	0

3. dp(1, 3)의 값은 dp(1, 2) + arr(1, 3)이다.

1	3	6
3	0	0
0	0	0

4. dp(2, 1)의 값은 dp(1, 1) + arr(2, 1)이다.

왜냐하면, 문제에서 요구하는 사이즈가 정해져 있기 때문이다.

(1, 1)에서 (2, 1)까지의 누적합에서는 y좌표가 1인 원소들만 더해줄 수 있다.

1	3	6
3	8	0
0	0	0

5. dp(2, 2)의 값은 (1, 1) + (1, 2) + (2, 1) + (2, 2)이다.

dp(2, 2) = dp(1, 2) + dp(2, 1) - dp(1, 1) + arr(2, 2)

로 나타낼 수 있다.

1. 바로 위에 행에서 저장해 놓은 누적 합에서 -> dp(2, 1)

2. 바로 왼쪽에서 저장해 놓은 누적 합을 더하고, -> +dp(2, 1)

3. 위에 행과, 왼쪽 행의 중복되는 누적 합을 빼준 후에, -> -dp(1, 1)

4. 현재 칸 (x, y)의 원소를 더해준다. -> +arr(2, 2)

 

위와 같은 순서대로 누적합을 저장해주면 된다.

• x좌표가 1이고 y좌표가 1일 때는 -> 최초의 값이므로 arr(1, 1) 입력
• y좌표가 1일 때는 -> x - 1, 즉 바로 위에 행의 dp(x - 1, 1)의 값에서 arr(x, 1)을 더해주면 된다.
• 그 이외일 때는 위에 예시의 5번에 나타낸 순서대로 더해주면 된다.

 

그렇다면 이제 구간에서 누적 합을 어떻게 구할 수 있을까?

 

구간 누적 합 구하기

1	3	6	10
3	8	15	24
6	15	27	42
10	24	42	64

예제 1번의 입력을 받았을 때, 위에서 설명한 방법으로 입력받아놓은 누적 합의 예시 표이다.

이 상황에서 (2, 2)부터 (3, 4)의 합을 구해보자.

 

1	3	6	10
3	8	15	24
6	15	27	42
10	24	42	64

• 파란색 배경은 우리가 구해야 하는 부분이다.
• 빨간색 글자는 (1, 1)에서 (3, 4)까지 누적합에서 빼줘야 하는 부분이다.
• 빨간색 배경은 두 번 빼주게 되므로 한 번은 더해줘야 하는 부분이다.

나는 빼줘야 되는 부분을 위에 부분과 왼쪽 부분으로 나누어서 구했다.

(2, 2)를 (x1, y1), (3, 4)를 (x2, y2)라고 했을 때,

 

1. 빼줘야하는 위 부분 : (1, 1)에서 (1, 4)까지의 합, 

점화식으로 나타내면 dp(x1 - 1, y2) 가 된다.

 

2. 빼줘야 하는 아래 부분 : (1, 1)에서 (3, 1)까지의 합,

점화식으로 나타내면 dp(x2, y1 - 1) 이 된다.

 

3. 두 번 빼주게 되는 부분 : (1, 1)까지의 누적 합

점화식으로 나타내면 dp(x1 - 1, y1 - 1) 이 된다.

 

두 번 빼주게 되는 부분이 값이 아니라 누적 합을 빼줘야 하는데,

만일 (3, 3)에서 (4, 4)의 구간 합을 구한다고 한다면,

dp(2, 3)을 빼고, dp(4, 2)를 빼주게 되는데, 이 경우 (1, 1) ~ (2, 2)까지 구간 합을 두 번 빼주게 된다.

따라서 그냥 원소값이 아닌, 누적 합을 빼줘야 한다.

1	3	6	10
3	8	15	24
6	15	27	42
10	24	42	64

 

이제 코드를 살펴보자.

사용한 변수와 STL

• widthHeight : 입력받는 N x N에서 N의 크기.
• sumCnt : 구간 합을 구하는 횟수
• arr 배열 : 입력받는 원소의 값
• dp 배열 : (1, 1)부터 (i, j)까지 누적 합을 저장해놓는 배열
• pointX1, pointY1, pointX2, pointY2 : 구간 합을 구할 때 입력받는 좌표
• ans : 구간 합을 구할 때 출력하는 변수.

메인함수 - 1

처음에 N의 크기와 구간 합의 횟수를 입력받는다.

그리고 나서, 각 표의 칸의 값을 입력받는다.

후에 입력받은 값을 토대로 (1, 1)부터 (i, j)까지의 누적합을 구해서 저장해둔다.

(1, 1)부터 (i, j)까지는

(1, 1) ~ (1, j)

(2, 1) ~ (2, j)

...

(i, 1) ~ (i, j)

이므로, 위에 행의 누적 합과 왼쪽 칸의 누적합을 더해준 후, 두 번 더해진 곳을 빼준 후 현재 칸의 값을 더해준다.

좌표가 0인 곳들은 0이 입력되어 있으므로 조건문에 구애받지 않고 구현할 수 있다.

 

메인함수 - 2

그리고 구간 합을 입력받은 횟수만큼 구해준다.

빼줄 윗 부분과 빼줄 왼쪽 부분, 그리고 두번 빼준 곳을 구한 후에

(1, 1)부터 (x2, y2)까지의 누적합에서 위 변수들을 활용해서 ans 정답 값을 구한 후 출력한다.

 

처음에 DP인 줄 알았지만 어떻게 더 시간을 줄일 수 있을까 고민을 많이했던 문제였다.

누적 합이라는 알고리즘을 오늘 배우게 되었다.

오랜만에 구현이 아닌 문제를 풀어보았는데, 확실히 뇌가 굳은 것 같았다.

 

GitHub - kimyunseok/study-record: my study-record

코드 전문은 위에서 확인이 가능하다.