글 읽기 - dp로 풀었는데 시간초과가 납니다

0917ba 4년 전 2

dp로 점화식 세워서 풀었는데 64% 부근에서 시간초과가 나네요... 64% 전까지는 빠르게 올라가던데...

나와있는 반례들 모두 통과했는데 뭐가 문제일까요?

(로직: n번째 포도주를 마실 때: n-1번째를 마실때와 안 마실때로 구분, n번째 포도주를 마시지 않는다면 n-1번째 포도주 dp로 실행)

#include<stdio.h>
int dp[10001]={0}, value[10001];
int max(int a, int b, int c){
    if(a>=b&&a>=c) return a;
    if(c>=b&&a<=c) return c;
    return b;
}
int podo(int n){
    if(n==0) return 0;
    if(n==1) return value[1];
    if(n==2) return value[1]+value[2];
    if(dp[n]!=0) return dp[n];
    dp[n]=max(podo(n-1), value[n]+podo(n-2), value[n]+value[n-1]+podo(n-3));
    return dp[n];
}
int main(){
    int n, i;
    scanf("%d", &n);
    for(i=1; i<=n; i++){
        scanf("%d", &value[i]);
    }
    printf("%d", podo(n));
    return 0;
}

skeep194 4년 전 4

포도주의 양은 음이 아닌 정수이므로 모두 0일 때 시간 초과가 발생할 수 있습니다.

podo함수 안에 있는 if(dp[n]!=0) 이 부분을 다른 방식으로 고쳐보세요.

0917ba 4년 전 0

감사합니다!!

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

문제

문제

출처

ICPC

dp로 풀었는데 시간초과가 납니다

0917ba 4년 전 2

skeep194 4년 전 4

0917ba 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말