코학다식

문제 링크 :: https://www.acmicpc.net/problem/11660 Solution 구간 합을 이용하긴 하는데 이차원 배열임을 유의해야 한다. 문제의 예시에서 볼 수 있듯이 그냥 처음부터 끝까지 수를 다 더하는 게 아니라 사각형 모양을 이루는 구간의 합을 구해야 한다. 이건 구간 합을 구할 때뿐만이 아니라, 부분 합을 구할 때도 마찬가지다. 특정 위치의 부분 합을 구하고 싶다면 처음(1, 1)부터 해당 위치까지 사각형을 만들어 그 구역에 있는 숫자들을 합해야 한다. 합하는 방법은 일차원 배열보다는 조금 복잡하지만 어렵지는 않다. 첫 행은 평범하게 부분 합 구하듯이 쭉쭉 더해 주면 된다. 다음 행부터는 첫 번째 열에 위치하는 경우와 아닌 경우가 달라진다. 첫 번째 열에 위치하면 만들 수 있..