3강 누적합 문제 4. 2차원 누적합
안녕하세요! 해당 문제 질문이 있습니다.
(2,2) 와 (2,4) 범위의 합을 구하는 문제인데
왜 (4,3)과 (3,2) 값을 구해서 빼주는 건가요?
그 전까지 설명해주시는 건 이해를 했는데 제대로 이해를 못한건지 마지막 출력 부분이 이해가 안되네요 ㅜㅠ
답변 1
0
마지막 부분 설명을 잘못했네요! 찾아 주셔서 감사합니다! 바로 수정해두겠습니다!
고쳐서 설명하자면 일단,
먼저 문제로부터 x1,y1,x2,y2로 입력을 받았고,
저는 2차원 배열 문제를 풀 때 [Y축][X축] 형태로 만들어서 문제를 풀고 있습니다!
그래서 문제를 보시면
(2,2)와 (3,4)의 범위의 합을 계산해야합니다.
이걸 제가 (X,Y)형태에서 (Y,X)형태로 바꾸면 (2,2)에서 (4,3)까지의 범위를 구하는 것이 됩니다.
그래서 정답은
prefix[4][3]까지의 합에서prefix[2][2]뒤의 범위를 빼줘야 함으로
prefix[y2][x2] - prefix[y2][x1-1] - prefix[y1-1][x2] + prefix[y1-1][x1-1]가 정답이 됩니다!
따라서, prefix[4][3] - prefix[4][1] - prefix[1][3] + prefix[1][1]가 정답입니다!
오늘 바로 수정해두겠습니다!
[4,3] - [1,3] - [4,1] + [1,1]
정답 완성!
1
강의 수정 완료 했고, 오늘 1시 반까지 재 업로드 완료 예정입니다 :)
sonjungwoo9@gmail.com 이 이메일로 연락주시면 커피랑 무료 수강권 전달해드리겠습니다. 진심으로 감사드립니다 :)
dp[x]가 최대값이라고 확신할수 있는 이유
0
43
1
1090번 문제 질문
0
148
1
유니온파인드
0
111
1
투포인터 25:15 질문
1
127
1
#1090번 문제 반례가 궁금합니다.
0
145
1
예제코드 자바입니다
1
186
1
정수론 파트 #2247 문제에 대한 질문입니다!
0
101
0
코드 오류
0
185
1
2강 정수론 문제3 #1407 질문
0
126
0
이차원 배열 (int형)dp로 0 혹은 -1로 체크하는 방법 말고 boolean형 배열로 체크해서 바로 리턴해줄 수 없나요?
0
154
0
1717번 최적화
0
112
0
백준 22988 문제 질문
1
192
2
[Python] 백준 1090번 문제
1
223
3
강의자료에서
1
161
2
2503 문제 제한 조건 질문!
1
248
2
백준 22988 번 문제
1
191
1
추가 강의 순서
1
179
2
(*문제 풀이)1090 테스트케이스 1번 C++
1
219
2
7강 RGB 색칠하기 질문 있습니다.
1
160
2
정수론 약수 빠르게 구하기 질문
1
254
1
1090 문제의 2, 3번째 아이디어는 결국 같은거 아닌가요?
1
372
2
1090 문제 관련하여 맨해튼 거리 최솟값에 대해 질문 있습니다.
1
220
2
누적합 문제 3번 질문
1
214
2
기억 ( 누적합 ) 강의 11660 문제
1
161
2