Gi-Log

문제 링크: https://www.acmicpc.net/problem/1749 1749번: 점수따먹기 동주는 항상 혼자 노느라 심심하다. 하지만 혼자 놀기의 고수가 된 동주는 매일매일 게임을 개발하여 혼자놀기의 진수를 우리에게 보여준다. 어느 날 동주는 새로운 게임을 개발하였다. 바로 점 www.acmicpc.net 문제 풀이에 이용된 알고리즘: 누적합, 다이나믹 프로그래밍 처음에는 만들 수 있는 모든 부분 행렬을 구하고, 각 부분 행렬 내 원소의 총 합 중 최대값을 구하는 방법에 대해서 생각해봤다. 부분 행렬을 결정하는 것은, 부분 행렬의 "좌측 상단"과 "우측 하단" 2가지 이다. 좌측 상단을 알고 있다면, 부분 행렬의 가로 길이와 세로 길이를 통해 우측 하단의 좌표를 구할 수 있다. 따라서 좌측 상..