[백준 / BOJ] 11660 구간 합 구하기 5

문제

출처 : www.acmicpc.net/problem/11660

11660번: 구간 합 구하기 5

N과 M이 주어지고, N*N그리드에 숫자들이 주어진다.

M개의 범위가 주어졌을때, 해당 범위에있는 숫자들의 합을 구하는문제다.

 

예를들어,

1 2 3 4

1 2 3 4

1 2 3 4

1 2 3 4

그리드에서, 1 1 1 4 는 10이다.

 

풀이

(구간합 구하기 3을 풀다 도망쳤다...)

일반적인 완전탐색으로는 풀지못한다.

N의 범위가 1024이고, M이 10만이므로, 완탐으로 풀려하면 1024*1024*100,000 만큼 반복한다.

 

처음에는 세로로 누적합을 구해놓고 가로길이의 차만큼 반복하는 방법으로 풀려했는데,

1 1 1 1

1 1 1 1

1 1 1 1

1 1 1 1

을

1 1 1 1

2 2 2 2

3 3 3 3

4 4 4 4

이런식으로 저장해놓고

한줄한줄 한번에 보는방법

이렇게해도, 가로길이가 최대 1024까지 증가하고, M이 10만이므로, 약 1억 2백만번 반복해서 시간초과가 나온다.

(이미 탐색한 위치가 반복해서 나온다면 바로 출력하는식으로 메모리제이션을 해주면 풀리긴할수도...?)

 

누적합을 가로 혹은 세로만 구하는게 아닌 가로 세로를 전부 저장해줘야한다. 

1 1 1 1

1 1 1 1

1 1 1 1

1 1 1 1

을

1 2 3 4

2 4 6 8

3 6 9 12

4 8 12 16

이런 형태로 저장해놓는다

 

저장할 dp식은 y-1위치의 저장된 dp값 + x-1위치 - 겹치는칸 이되어서

dp[y][x] = arr[y][x] + dp[y-1][x] + dp[y][x-1] - dp[y-1][x-1]

이 된다.

 

구할때도 비슷하게 해주면되는데,

1. (1,1)부터 (x2,y2)의 dp값을 구해놓는다.

2. 1번에서 구해놓은값에 (x1, y1) ~ (x2, y2) 사이에 속하지 않는값들을 빼주면되는데, 이때, 겹치는부분은 두번 빼주게되므로 겹치는 부분을 한번 더해준다.

총 식은

dp[x2][y2] - dp[x-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1]

이다.

 

상수시간만에 범위에속한값을 구하므로, M번의 반복으로 답을 찾을수있다.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/11660%20%EA%B5%AC%EA%B0%84%20%ED%95%A9%20%EA%B5%AC%ED%95%98%EA%B8%B0%205/main.cpp

devxb/JJUNalgo