글 읽기 - 시간복잡도 O(n)인데 왜 시간초과가 날까요??ㅜㅜ

sky0331 6년 전 0

나름 데이터는 잘 나오는 거 같은데...

시간초과가 나네요ㅠㅠ

시간복잡도가 O(n)인데 시간초과가 왜 나는걸까요ㅠ

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

int dx[5]={0,1,0,-1,0};
int dy[5]={0,0,1,0,-1};
int dp[10001],top,bot,i,j,k,n,q,w,e,low,no,high,mid,cnt,sum,maxi;
int num,now,ok,m,x,y,z,tx,ty,len,mini,st[1001],check[1001];
int checkk[1001][1001],a[10001],aa[1001][1001],b[1001];
char c,s[1001],ss[1001][1001],s1[1001],s2[1001],s3[1001];
long long ll;

int maxf(int m,int n)
{
    if(m>n)
        return m;
    return n;
}

int main(void){
    scanf("%d",&n);

    for(i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        if(i==1)
            dp[1]=a[1];
        else if(i==2)
            dp[2]=a[1]+a[2];
        else
            dp[i]=a[i]+maxf(dp[i-3]+a[i-1],dp[i-2]);
        if(maxi<dp[i])
            maxi=dp[i];
    }
    printf("%d",maxi);
}

sk7755 6년 전 0

음 일단 와인 최대가 10000개 아닐까요?

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

문제

문제

출처

ICPC

시간복잡도 O(n)인데 왜 시간초과가 날까요??ㅜㅜ

sky0331 6년 전 0

sk7755 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말