글 읽기 - 왜 런타임 에러인가요ㅠ,ㅠ

illiboy1212 4년 전 0

지적해주시면 감사하겠습니다ㅠ,ㅠ

#include <cstdio>

bool check[2600000];

int main() 
{
    int n;
    int p, q;
    int siz = 0;
    int min = 0;
    int sum = 0;
    int k;
    int arr[10000];
    int input[15];
    check[0]=1;
    arr[0]=0;

    scanf("%d" ,&n);

    for (int i = 0; i < n; i++)
    {
        scanf("%d", &input[i]);
        sum+= input[i];
    }

    for (int i = 0; i < n; i++)//추가값
    {
        k=0;
        for (int j = 0; j<=siz; j++)//기존값
        {
            p = arr[j]+input[i];
            q = arr[j]-input[i];

            if (q<0)
            {
                q*=(-1);
            }

            if (check[q]==0)
            {
                k++;
                arr[siz+k]=q;
                check[q]=1;
            }

            if (check[p]==0)
            {
                k++;
                arr[siz+k]=p;
                check[p]=1;
            }

        }
        siz+=k;
    }

    printf("%d\n", sum-siz);
}

evenharder 4년 전 1

arr이 표현 가능한 수들을 저장하는 역할인 것 같은데, 10000개 이상의 무게를 표현할 수 있는 경우가 있어서 런타임 에러가 나는 것입니다.

상당히 크게 (약 50만~100만) 정도로 저장하시는 걸 권장합니다.

그리고 크기가 큰 배열은 직접 함수 내에서 선언하기보다는 전역 변수로 하거나, C++의 vector 등을 동해 동적으로 메모리를 관리하는 편이 좋습니다.

밑의 첨부한 예시의 경우, siz가 최종적으로 465720까지 도달하게 됩니다.

예시 입력
13
1 3 9 27 81 243 729 2187 6561 19683 59049 177147 200000

예시 출력
0

부가 설명
입력이 1, 3, 3^2, 3^3, ..., 3^(n-1), 3^n 꼴로 들어오면 '빈틈 없이' 무게를 잴 수 있습니다.
증명은 수학적 귀납법으로 할 수 있습니다.
첫 12개의 수는 3의 거듭제곱 꼴이며, 마지막만 문제 조건에 맞춘 200000입니다.

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

문제

문제

출처

ICPC

왜 런타임 에러인가요ㅠ,ㅠ

illiboy1212 4년 전 0

evenharder 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말