글 읽기 - 시간 초과 뜨는데 이 소스의 시간 복잡도를 알 수 있을까요?

andrealgorithm 5년 전 0

이나믹 프로그래밍 입문자입니다. Top -down 방식으로 풀고 있는데. for문 하나만 돌렸기때문에 시간복잡도는

그리 크지 않았다고 생각했는데 시간초과가 발생했네요.. 조언을 구할수 있을까요?

#include <cstdio>
using namespace std;

int arr[10002]={0};
int main(){
    int n;
    scanf("%d",&n);
    
    for(int i=1; i<=n; i++){
        scanf("%d",&arr[i]);
    }
    int cnt =0;
    cnt += arr[n];
    
    for(int i =n; n>=1; ){
        if(arr[i-1] >arr[i-2]){
            if(i-1 <0) break;
            cnt +=arr[i-1];
            i = i-1;
        }
        else if(arr[i-1] <arr[i-2]){
            if(i-2 <0) break;
            cnt +=arr[i-2];
            i= i-2;
        }
    }
    printf("%d",cnt);
    return 0;
}

zxcvber 5년 전 0

for 문 내부의 두 if 문의 조건이 이상한것 같습니다.

다음 반례에서 시간 초과가 납니다

Input:

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

문제

문제

출처

ICPC

시간 초과 뜨는데 이 소스의 시간 복잡도를 알 수 있을까요?

andrealgorithm 5년 전 0

zxcvber 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말