[Week of DP] BOJ 11660 #1

이번에 풀 문제는 구간 합 구하기 5

www.acmicpc.net/problem/11660

 

일단 구조만 봤을 때는

가로로 누적합을 구한 배열과

세로로 누적합을 구한 배열을 구한 뒤

 

결과적으로 가로 세로 누적합을 구하면 될 것 같아 보인다.

 

누적합은 보통

1~5의 index가 있을 시

1은 1의 값

2는 1+2의 값

3은 1+2+3의 값

4는 1+2+3+4의 값

5는 1+2+3+4+5의 값을 구한 뒤에

 

4~5의 값은

5의 누적합 빼기 4의 누적합을 구하면 나오는 식이다.

 

일단 전략은 세웠으니 검증을 해봐야 되는데.. 아직 거기까진 못해봤다.

 

다음 포스팅에서 시도해 볼 예정이다.