글 읽기 - 이 소스로는 답이 없는 소스인가요

zmfldlwl 7년 전 0

O(n^4)으로 풀어야 풀린다고 솔루션에 적혀있던데

해당 솔루션으로 최적화 할 방법이 없을까요... 답은 나오던데

#define _CRT_SECURE_NO_WARNINGS

/*

VCPP, GPP에서 사용

*/

#include <stdio.h>
#include <iostream>
using namespace std;

int n;
int arr[55][55];
int t_arr[55][55];

int main()
{

    //int nCount;      /* 문제의 테스트 케이스 */

    //cin >> nCount;   /* 테스트 케이스 입력 */

    //for (int itr = 0; itr<nCount; itr++)
    //{

    //    cout << "#testcase" << (itr + 1) << endl;

    //    /*

    //    알고리즘이 들어가는 부분

    //    */

    //}

    scanf("%d", &n);

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            scanf("%d", &arr[i][j]);
        }
    }

    //sub-sum 전처리

    t_arr[1][1] = arr[1][1];

    for (int i = 2; i <= n; i++)
    {
        t_arr[1][i] += arr[1][i] + t_arr[1][i - 1];

        t_arr[i][1] += arr[i][1] + t_arr[i - 1][1];
    }

    for (int i = 2; i <= n; i++)
    {
        for (int j = 2; j <= n; j++)
        {
            t_arr[i][j] = t_arr[i - 1][j] + t_arr[i][j - 1] + arr[i][j] - t_arr[i - 1][j - 1];
        }
    }

    int res = 0;

    for (int i = 2; i <= n; i++)
    {
        for (int j = 2; j <= n; j++)
        {
            //i,j는 중간점
            //왼쪽 상단 오른쪽 하단인 경우
            for (int x = 1; x < i; x++)
            {
                for (int y = 1; y < j; y++)
                {
                    //x,y 는 1번의 시작점
                    for (int a = i + 1; a <= n + 1; a++)
                    {
                        for (int b = j + 1; b <= n + 1; b++)
                        {
                            //a,b 는 2번의 끝점
                            //x,y ~ i,j 의 구간합과
                            int sub_sum1 = t_arr[i - 1][j - 1] - t_arr[i - 1][y - 1] - t_arr[x - 1][j - 1] + t_arr[x - 1][y - 1];
                            //i,j ~ a,b 의 구간합이 같다면
                            //res++
                            int sub_sum2 = t_arr[a - 1][b - 1] - t_arr[a - 1][j - 1] - t_arr[i - 1][b - 1] + t_arr[i - 1][j - 1];

                            if (sub_sum1 == sub_sum2)
                                res++;
                        }
                    }
                }
            }

            //오른쪽 상단, 왼쪽 하단인 경우
            for (int x = 1; x < i; x++)
            {
                for (int y = j + 1; y <= n + 1; y++)
                {
                    for (int a = i + 1; a <= n + 1; a++)
                    {
                        for (int b = 1; b < j; b++)
                        {
                            //x,y ~ i,j 의 구간합
                            int sub_sum1 = t_arr[i - 1][y - 1] - t_arr[i - 1][j - 1] - t_arr[x - 1][y - 1] + t_arr[x - 1][j - 1];

                            //i,j ~ a,b의 구간합
                            int sub_sum2 = t_arr[a - 1][j - 1] - t_arr[a - 1][b - 1] - t_arr[i - 1][j - 1] + t_arr[i - 1][b - 1];

                            if (sub_sum1 == sub_sum2)
                                res++;
                        }
                    }
                }
            }
        }
    }

    printf("%d\n", res);

    return 0;   /* 반드시 return 0으로 해주셔야합니다. */

}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

이 소스로는 답이 없는 소스인가요

zmfldlwl 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말