글 읽기 - 시간초과 질문입니다.

lg970325 7년 전 0

계속 고쳤는데

연산수도 별로 없는것 같은데 계속 시간초과가 뜨네요.....

해결법을 알려주세요ㅠㅠ

#include<stdio.h>
#include<stdlib.h>

int main(void)
{
    int n,k,i,j;
    scanf("%d %d",&n,&k);
    
    int** arr=(int**)malloc(sizeof(int*)*(n+1));
    for(i=0;i<=n;i++)
        arr[i]=(int*)malloc(sizeof(int)*(n+1));
    
    int** map=(int**)malloc(sizeof(int*)*(n+1));
    for(i=0;i<=n;i++)
        map[i]=(int*)malloc(sizeof(int)*(n+1));
    
    int** ask=(int**)malloc(sizeof(int*)*k);
    for(i=0;i<k;i++)
        ask[i]=(int*)malloc(sizeof(int)*4);
    
    int* sum=(int*)calloc(sizeof(int),k);
    
    for(i=0;i<=n;i++)
    {
        map[0][i]=0;
        map[i][0]=0;
        arr[0][i]=0;
        arr[i][0]=0;
    }
    
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            scanf("%d",&arr[i][j]);
            map[i][j]=arr[i][j];
            arr[i][j]+=arr[i][j-1];
        }
        for(j=1;j<=n;j++)
            arr[i][j]+=arr[i-1][j];
    }
    
    for(i=0;i<k;i++)
    {
        for(j=0;j<4;j++)
            scanf("%d",&ask[i][j]);
    }
    
    for(i=0;i<k;i++)
    {
        sum[i]+=arr[ask[i][2]][ask[i][3]];
        sum[i]-=arr[ask[i][2]][ask[i][1]];
        sum[i]-=arr[ask[i][0]][ask[i][3]];
        sum[i]+=arr[ask[i][0]][ask[i][1]];
        
        for(j=ask[i][0];j<=ask[i][2];j++)
            sum[i]+=map[j][ask[i][1]];
        
        for(j=ask[i][1];j<=ask[i][3];j++)
            sum[i]+=map[ask[i][0]][j];
        
        sum[i]-=map[ask[i][0]][ask[i][1]];
    }
    
    for(i=0;i<k;i++)
        printf("%d\n",sum[i]);
    
    return 0;
}

yclock 7년 전 1

위 소스의 시간복잡도는 O(N²+NM)으로 NM이 최대 10⁹까지 갈 수 있는 이 문제를 제한시간 내에 풀기는 어렵습니다.

부분합 문제의 접근 방법은 맞습니다. 그러나 합을 더하고 빼는 부분을 다르게 처리하면 O(1)으로 부분합을 구할 수 있습니다.

또는 첨부된 부분에서 다음과 같은 배열을 하나 선언해서 풀 수도 있습니다.

        // 문제의 부분
        for(j=ask[i][0];j<=ask[i][2];j++)
            sum[i]+=map[j][ask[i][1]];
         
        for(j=ask[i][1];j<=ask[i][3];j++)
            sum[i]+=map[ask[i][0]][j];

    // 만약 다음과 같이 정의된 배열이 있다면...?
    int lineSum[][];
    lineSum[P][Q] = sigma(i=0; i<=Q; map[P][i]); // lineSum[P][Q] = map[P][0] + map[P][1] + ... + map[P][Q]

lg970325 7년 전 1

감사합니다!

문제의 부분을 고쳤더니 성공했습니다.

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

문제

문제

출처

ICPC

시간초과 질문입니다.

lg970325 7년 전 0

yclock 7년 전 1

lg970325 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말