백준 11660번 구간 합 구하기 5

< 백준 11660번 구간 합 구하기 5 - 마포 코딩박 >

사용한 알고리즘: Prefix Sum ( 구간합 배열 )


 이차원 배열에서 구간합 배열을 구하는 문제였습니다.

문제풀이는 다음과 같습니다.

(1) (코드 5~6)
 'pSum[x][y]: x행의 1~y 열의 합' 이라고 설정해주었습니다.

(2) (코드 11~19)
 각 i 행별로 1~N의 열들의 값을 입력받으며 pSum[i][1~N] 값을 구해줍니다.

(3) (코드 19~26)
 입력받은 (x1, y1) ~ (x2, y2) 까지의 성분합을 계산하여 출력해줍니다.
 x1<=x<=x2 행들을 보면서 pSum[x][y2] - pSum[x][y1-1] 을 구해 더해주면됩니다.