문제링크 : https://www.acmicpc.net/problem/11660
11660번: 구간 합 구하기 5
첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네
www.acmicpc.net
작성코드
해설
입력받은 x1,y1, x2,y2의 값들을 매번 계산하게 된다면 테스크 케이스, 좌표값 차이가 커질 경우 연산 시간을 감당하기 힘들어진다.
이를 위해 누적합을 저장해주고 이를 활용하여 값을 출력해준다.
1. 누적합 계산하기
누적합 값을 계산할 dp 표를 만든다.
N x N 의 표에서는 1,1 부터 시작하므로
계산을 편리하게 하기 위해서 0인 행열을 추가해주었다.
누적합을 계산하기 위해 앞 결과를 참고하여 만드려면 아래와 같다.
2,2를 계산하기 위해서
앞서 계산된 1,2 누적 값과 2,1 누적값을 더한 뒤 겹쳐지는 1,1의 값을 제거해준다. 그리고 마지막으로 2,2의 값을 더해주면
누적값 계산이 가능하다. 이를 코드로 작성하면 이와 같다.
2. 구간 합 구하기
누적 합을 이용하여 구간 합을 구하려면 누적합을 사용해 닿지 않는 부분을 뺴야한다.
예를 들어 2,2, 3,3 일 경우
아래 영역 값을 구해야 한다.
이를 코드로 작성하면 아래와 같다.
'백준 > Python' 카테고리의 다른 글
| [백준] 1931 회의실 배정 (python 파이썬) (0) | 2023.01.10 |
|---|---|
| [백준] 11047 동전 0 (python 파이썬) (0) | 2023.01.02 |
| [백준] 26217 별꽃의 세레나데(Easy) (python 파이썬) (0) | 2022.12.22 |
| [백준] 26215 눈 치우기 (python 파이썬) (0) | 2022.12.22 |
| [백준] 2559 수열 (python 파이썬) (0) | 2022.12.07 |