글 읽기 - 붕어빵 판매하기 시간초과 질문입니다.

kjho1037 6년 전 0

붕어빵 판매하기 시간초과 실문드립니다.

재귀로 문제를 풀려고 하였는데...계속 시간초과가 뜨네요.

그래서 다른 분이 같은 문제를 재귀로 풀으셔서 소스를 봤더니

거의 비슷한 것 같은데 이건 0ms로 맞았다고 뜨네요..

차이점이 무었인지 질문드립니다!

//////////////////////제가 작성한 코드입니다.
#include <stdio.h>
int N, arr[1001],max,D[1001];

int DP(int n,int total)
{
	if (n < 0) return 0;
	else if (D[n]) return D[n];
	else if (n == 0) {
		if (max < total)max = total;
		return max;
	}
	for (int i = 1; i <= N; i++)
	{
		total += arr[i];
		D[n] = DP(n - i, total);
		total -= arr[i];
	}
	return D[n];
}

int main()
{
	scanf("%d",&N);
	for (int i = 1; i <= N; i++)
		scanf("%d",&arr[i]);
	DP(N, 0);
	printf("%d",max);
	return 0;
}

//////////////////////http://blog.pj-room.com/80 에 포스팅된 코드입니다.
#include <iostream>
#include <algorithm>
using namespace std;
int P[1001];
int DP[1001];
int dp(int N) {
    if (N <= 0) return N;
    if (DP[N] > 0) return DP[N];
 
    for (int i = 1; i <= N; i++) {
        DP[N] = max(DP[N], dp(N - i) + P[i]);
    }
 
    return DP[N];
}
int main() {
    int N;
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> P[i];
    }
 
    cout << dp(N) << endl;
    return 0;
}

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

문제

문제

출처

ICPC

붕어빵 판매하기 시간초과 질문입니다.

kjho1037 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말