글 읽기 - 어떻게 풀어야 할 지 모르겠습니다.

rootsquare 3년 전 0

아무리봐도 브루트포스 외의 방법이 생각나지 않습니다. 배열에 있는 수들 사이에 규칙이 없으니까요...

그렇다고 아래의 코드처럼 일일이 다 확인해보면 시간 초과가 날 것입니다.

네 개의 배열을 두 개씩 짝지어서(예: A,B 와 C,D) 각각의 합으로 이루어진 배열 2개로 압축시킨 다음 브루트포스 돌려도 시간에 걸릴 것 같습니다.

(합 배열은 최대 길이가 1600만)

혹시 더 좋은 방법이 있을까요?

#include<stdio.h>
int main(void)
{
    int a[4010]={0},b[4010]={0},c[4010]={0},d[4010]={0};
    int num,i,j,k,l;
    long long answer=0;
    scanf("%d",&num);
    for(i=1; i<=num; i++)
    {
        scanf("%d %d %d %d",&a[i],&b[i],&c[i],&d[i]);
    }
    for(i=1; i<=num; i++)
    {
        for(j=1; j<=num; j++)
        {
            for(k=1; k<=num; k++)
            {
                for(l=1; l<=num; l++)
                {
                    answer+=((a[i]+b[j]+c[k]+d[l])==0);
                }
            }
        }
    }
    printf("%lld",answer);
    return 0;
}
//당연히 답은 맞게 나오겠지만, 시간 복잡도가 O(N^4)나 됩니다. 분명히 시간초과가 날 것입니다.

evenharder 3년 전 1

세 번째 줄에서 말씀하신 방향을 조금 더 개선해보시면 됩니다.

이에 대한 정당성은 바로 이전 질문글을 참고하시면 좋을 것 같습니다 (풀이와 해설이 바로 나와 있으므로, 조금 생각해보신 다음에 읽어보심을 추천드립니다).

rootsquare 3년 전 0

Upper_bound,lower_bound로 양 끝 범위를 구해서 답을 구한 결과 해결했습니다.

조언 감사드립니다!!

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

문제

문제

출처

ICPC

어떻게 풀어야 할 지 모르겠습니다.

rootsquare 3년 전 0

evenharder 3년 전 1

rootsquare 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말