글 읽기 - 시간초과....

moonsj9595 8년 전 0

시간초과 어떻게 줄일까요ㅠㅠ

c[i][q]= xCi입니다

마음같아선 xCi를 배열로 만들고싶은데 1000000하니까 메모리가 너무 커서 안되더라구요

도와주세요ㅠㅠ

#include<stdio.h>
#include<string.h>
long long int arr[1000001], c[1000001][2], q, fac[1000001], P=1000000000;
int n;
long long int f (int x){
    long long int tmp;
    int i;
    if(x==1) return 0;
    if(x==2) {
        return 1;
    }
    if(arr[x]!=0) return arr[x];
    q=x%2;
    fac[x]=x*fac[x-1];
    fac[x]%=P;
    c[0][q]=1;
    for(i=1;i<=x;i++){
        c[i][q]=c[i-1][1-q]+c[i][1-q];
        c[i][q]%=P;
    }
    arr[x]+=fac[x-1];
    for(i=1;i<=x-2;i++){
        tmp=c[i][1-q]*f(i+1);
        tmp%=P;
        tmp*=f(x-1-i);
        tmp%=P;
        arr[x]+=tmp;
        arr[x]%=P;
    }
    q=1-q;
    return arr[x];
}
int main(){
    arr[2]=1;
    c[0][0]=1;
    c[1][0]=2;
    c[2][0]=1;
    fac[2]=2;
    int i=0;
    fac[1]=1;
    scanf("%d", &n);
    for(i=1;i<=n;i++) f(i);
    printf("%lld", arr[n]);
     
    return 0;
}

game2k 8년 전 1

http://j1w2k3.tistory.com/667

참고가 될 것 같습니다

moonsj9595 8년 전 0

@game2k 이미 점화식과 일반식은 알고 있는 상황이었어요ㅎㅎ

dp로 풀어보고 싶어서 한건데 생각보다 쉽지 않군요ㅠ

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

문제

문제

출처

ICPC

시간초과....

moonsj9595 8년 전 0

game2k 8년 전 1

moonsj9595 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말