백준 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] 을 구해 더해주면됩니다.
사용한 알고리즘: 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] 을 구해 더해주면됩니다.
댓글
댓글 쓰기
긴 글 읽어주셔서 감사합니다.
궁금한게 있으시다면 댓글 달아주세요!