[23247] - Ten

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

23247번: Ten

문제 해석

2차원 배열이 주어지고 그 안 에 사각형을 그렸을 때, 숫자들의 합이 10이 되는 사각형의 개수를 구하기.

 

풀이

- 입력 부분에 힌트가 있는데, $$1\leq p_{ij} \leq10$$ 이 부분을 잘 보면 각 값의 범위가 1부터 10이라는 뜻으로, 사각형의 최대 크기가 10, 최소크기가 1이라는 것을 알 수있다.

 

1. 입력 받은 배열을 누적 합 시키기

2. 시작 범위부터, 끝 범위(최대 10)까지 탐색하며 조건에 맞으면 카운트 올리기

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

namespace Baekjoon.Silver
{
    class _23247
    {
        static void Main(string[] args)
        {
            int[] n = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            int[][] arr = new int[n[0]][];
            int count = 0;

            for (int i = 0; i < n[0]; i++)
                arr[i] = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

            //누적 합
            int[,] sum = new int[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] = sum[i, (j - 1)] + arr[i - 1][j - 1] + sum[i - 1, j] - sum[i - 1, j - 1];
            }

            /*
            Console.WriteLine();
            for (int i = 1; i <= n[0]; i++)
            {
                for (int j = 1; j <= n[1]; j++)
                    Console.Write(sum[i, j] + " ");
                Console.WriteLine();
            }

            */

            //시작 범위
            for (int i = 1; i <= n[0]; i++)
            {
                for (int j = 1; j <= n[1]; j++)
                {
                    //끝 범위
                    for (int ii = 0; ii < 10; ii++)
                    {
                        for (int jj = 0; jj < 10; jj++)
                        {
                            if(i+ii <= n[0] && j+jj <= n[1])
                            {
                                 if (sum[i+ii, j+jj] - sum[i + ii, j -1] - sum[i - 1, j + jj] + sum[i - 1, j - 1] == 10)
                                {
                                    //Console.WriteLine($"{sum[i+ii, j+jj]} - {sum[i + ii, j -1]} - {sum[i - 1, j + jj]} + {sum[i - 1, j - 1]}");
                                    count++;
                                }
                            }

                        }
                    }
                }
            }
            
            Console.WriteLine(count);
        }
    }
}