글 읽기 - 스티커: Top-down 방법을 이용했는데 시간초과가 걸려요

mtb7390 5년 전 0

안녕하세요 알고리즘을 공부하고 있는 초보입니다. 스티커 문제에서 Bottom-up 방식으로 문제를 풀때는 괜찮았는데, Top-down 방식으로도 문제를 푸니깐 98-99%에서 시간 초과가 걸리네요.

빈번한 재귀호출 때문에 그럴 수도 있고 다른 이유로 문제가 발생했을 듯한데 어디에 문제가 있는지 도움을 요청 드려도 괜찮을까요?

#include <iostream>
using namespace std;
const int N = 100000;
const int M = 2;
long long d[N+1][M];
long long p[N+1][M];
long long go(int n, int m)
{
    if (n<=1) return p[n][m];
    if (d[n][m]) return d[n][m];
    if (m==0)
    {   
        d[n][m] = max(go(n-1,1), go(n-2,1)) + p[n][m];
    }   
    else
    {   
        d[n][m] = max(go(n-1,0), go(n-2,0)) + p[n][m];
    }   
    return d[n][m];
}
int main()
{
    int t; scanf("%d",&t);
    while (t--)
    {   
        long long ans = 0;
        int n; scanf("%d",&n);
        for (int i = 1; i <= n; i++) scanf("%lld",&p[i][0]);
        for (int i = 1; i <= n; i++) scanf("%lld",&p[i][1]);
        for (int i = 3; i <= n; i++)
        {   
            ans = max(go(i, 0), go(i, 1));
        }   
        printf("%lld\n", ans);
        for (int i = 0; i <= n; i++)
        {
            d[i][0] = d[i][1] = 0;
            p[i][0] = p[i][1] = 0;
        }
    }
    return 0;
}

kyo20111 5년 전 1

시간초과가 날때는 언제나 최악의 경우를 생각해보세요.

100000

0 0 0 0 0 ...

이런식으로 입력이 들어올때 어떻게 될까요?

kyo20111 5년 전 1

dp에 들어 올 수 있는 값을 예외값으로 지정하면 안됩니다!

mtb7390 5년 전 1

감사합니다!! 답변달아주셔서!! 말씀주신대로 예외처리에 해당하는 부분을 수정하니깐 잘 되네요!! ㅎㅎ

#include <iostream>
using namespace std;
const int N = 100000;
const int M = 2;
long long d[N+1][M];
long long p[N+1][M];
long long go(int n, int m)
{
    if (n==0) return 0;
    if (n==1) return p[n][m];
    if (d[n][m]!=-1) return d[n][m];
    if (m==0)
    {   
        d[n][m] = max(go(n-1,1), go(n-2,1)) + p[n][m];
    }   
    else
    {   
        d[n][m] = max(go(n-1,0), go(n-2,0)) + p[n][m];
    }   
    return d[n][m];
}
int main()
{
    int t; scanf("%d",&t);
    while (t--)
    {   
        for (int i = 0; i <= N; i++)
        {   
            d[i][0] = d[i][1] = -1; 
            p[i][0] = p[i][1] = -1; 
        }   
        long long ans = 0;
        int n; scanf("%d",&n);
        for (int i = 1; i <= n; i++) scanf("%lld",&p[i][0]);
        for (int i = 1; i <= n; i++) scanf("%lld",&p[i][1]);
        for (int i = 3; i <= n; i++)
        {
            ans = max(go(i, 0), go(i, 1));
        }
        printf("%lld\n", ans);
    }
    return 0;
}

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

문제

문제

출처

ICPC

스티커: Top-down 방법을 이용했는데 시간초과가 걸려요

mtb7390 5년 전 0

kyo20111 5년 전 1

kyo20111 5년 전 1

mtb7390 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말