[9639] - Omar Loves Candies

https://www.acmicpc.net/problem/9639

9639번: Omar Loves Candies

문제 해석

직사각형이 주어졌을 때 하위 직사각형 내부의 합이 최대가 되는것을 찾으면 된다.

• 주의할점 - 첫번째 열/행을 제외하고 모든 칸의 점수는 왼쪽, 위보다 크다. (이걸 안읽고 풀어서 틀림)

 

문제 풀이

누적합 문제였다.

- 먼저 각 칸을 누적시켜 저장한다.

- 그 후 오른쪽 맨 아래칸을 기준으로 반복하며 최대값을 찾으면 된다.

- 노란색 부분을 찾고 싶으면 노란색 가장 우측 하단값 에서 빨간색 부분과 파란색 부분을 뺀 뒤, 두번 빼진 보래색 부분을 한번 더해주면 된다.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Baekjoon
{
    class _9639
    {
        static void Main(string[] args)
        {
            StringBuilder stb = new StringBuilder();
            int t = int.Parse(Console.ReadLine());
            for(int test = 0; test<t; test++)
            {
                int[] n = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
                int[][] arr = new int[n[0]][];
                for(int i = 0; i < n[0]; i++)
                    arr[i] = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

                //누적합
                long[,] sum = new long[n[0]+1, n[1]+1];
                for(int i = 1; i <= n[0]; i++)
                {
                    for (int j = 1; j <= n[1]; j++)
                        sum[i, j] = arr[i - 1][j - 1] + sum[i, j - 1] + sum[i - 1, j] - sum[i-1,j-1];
                }

                long max = sum[n[0],n[1]];
                for(int i = 0; i < n[0]; i++)
                {
                    for(int j = 0; j < n[1]; j++)
                    {
                        if (max < sum[n[0], n[1]] - sum[i, n[1]] - sum[n[0], j] + sum[i, j])
                            max = sum[n[0], n[1]] - sum[i, n[1]] - sum[n[0], j] + sum[i, j];
                    }
                }

                stb.AppendLine(max.ToString());
            }

            Console.WriteLine(stb);
        }
    }
}