오구의코딩모험

https://www.acmicpc.net/problem/1749 문제 3줄 요약1. 동주와 점수 따먹기 게임을 한다.2. N*M 행렬 각 칸에 -10'000 ~ 10'000의 정수를 하나씩 쓴다.3. 행렬의 부분 행렬의 합이 최대가 되게 구하라!   예제를 보고누적합을 생각하니 DP를 사용해야겠는데?라는 생각이 떠올랐고풀었던 유사한 문제가 생각났다.  https://59travel.tistory.com/104 [C++] BOJ 15724번 : 주지수https://www.acmicpc.net/problem/15724 문제 3줄 요약1. 네모 왕국의 1X1의 단위 구역을 여러 개 묶으려고 한다.2. 4개의 숫자로 직사각형 범위를 알려준다.3. 해당 직사각형 범위의 내에 살고 있는 사람 수를59travel...

https://www.acmicpc.net/problem/15724 문제 3줄 요약1. 네모 왕국의 1X1의 단위 구역을 여러 개 묶으려고 한다.2. 4개의 숫자로 직사각형 범위를 알려준다.3. 해당 직사각형 범위의 내에 살고 있는 사람 수를 구해보자.  DP가 아닌 완전 탐색으로 처음 접근했더니시간 초과로 통과가 되지 않았다..! 직사각형의 시작 좌표와 (1,1)가고정이 아니기에 DP 테이블을 사용할 수 있나? 에 대한의문이 생겼다. 결국 코딩도사인 GPT에게DP를 어느 부분에 적용하면 좋을지 도움을 받았다.  DP 테이블에 (1, 1)부터 해당 좌표까지의직사각형 합을 저장(메모이제이션) 해두는 것이었다. 그 후(1, 1) 부터 (x1, y1) 의 인원 수와(1, 1) 부터 (x2, y2) 의 인원 수..