글 읽기 - 게시판에 있는 반례들은 다 만족시켰는데

minripex 3년 전 0

질문1.시간초과문제는 불필요한 재귀함수를 써서 그런걸까요?

질문2.재귀함수가 시간복잡도 성능을 떨어뜨린건가요?

질문3.제가 푼방법은 DP로 푼문제가아니죠?

#include<bits/stdc++.h>
using namespace std;
int n;
int step[301]={0,};

int dp(int x)
{
	if(x<1)return 0;
	else if(x==1)
	{
		return step[n];
	}
	else if(n>2&&x==2)
	{
		return step[n];
	}
	else if(n==2&&x==2)
	{
		return step[n-1]+step[n];
	}
	else if(x==3)
	{
		int a,b;
		a=step[n-2]+step[n];
		b=step[n-1]+step[n];
		return max(a,b);
	}
	else if(n>4&&x==4)
	{
		int a,b;
		a=step[n-2]+step[n];
		b=step[n-3]+step[n-1]+step[n];

		return max(a,b);
	}
	else if(n==4&&x==4)
	{
		int a,b,c;
		a=step[n-2]+step[n];
		b=step[n-3]+step[n-1]+step[n];
		c=step[n-3]+step[n-2]+step[n];
		return max({a,b,c});
	}
	else if(x>=5&&x==n)
	{
		int e,f,g;
		e=step[n-x+2]+dp(x-2);
		f=step[n-x+1]+step[n-x+3]+dp(x-3);
		g=step[n-x+1]+step[n-x+2]+step[n-x+4]+dp(x-4);
		return max({e,f,g});
	}
	else if(x>=5&&x<n)
	{
		int e,f;
		e=step[n-x+2]+dp(x-2);
		f=step[n-x+1]+step[n-x+3]+dp(x-3);

		return max(e,f);
	}
}
int main()
{

	int num;
	cin>>n;
	for(int i=1;i<=n;++i)
	{
		cin>>num;
		step[i]=num;
	}
	cout<<dp(n);
	
	
}

1207koo 3년 전 1

일단 문제는 안 읽었고 안 풀어서 틀릴 수 있습니다

x>=5일 때를 보면 dp(x-2),dp(x-3)을 호출하는데, 이런 식으로 하면 동일한 계산을 반복하게 됩니다.

예를 들어서 dp(x-2)에서도 dp(x-5)를 호출할 것이고, dp(x-3)에서도 dp(x-5)를 호출하겠죠. 그런데 제 생각에는 dp(x-5)의 값은 언제 불러도 같은 것 같은데, 값을 계산하는 것을 반복하게 됩니다.

더 들어가면 dp(x)는 dp(x-5)를 두 번 호출하고, 그러면 각각에서 dp(x-10)을 두 번씩 호출해서 4번 호출하고, ... 해서 dp(x-100)은 최소한 100만 번은 호출되게 됩니다.

함수의 값을 리턴하기 전에 결과를 어딘가에 저장하고, 다시 호출될 경우 그 값을 리턴하는 식으로 하는 것이 좋습니다.

minripex 3년 전 0

피드백 감사합니다!!

혈을 뚫어주셨습니다

minripex 3년 전 0

그런데 저렇게 푼 방식이 DP라고 할 수 있나요?

1207koo 3년 전 0

사실 DP라고 볼 순 없겠죠...? DP의 핵심이 저런 반복적인 연산을 줄이는 것이니깐요

minripex 3년 전 0

알고리즘공부를 시작한지 얼마 안되서

좀 더 역량을 키운뒤 다시한번 풀어봐야겠네요 답변 정말 감사합니다!

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

문제

문제

출처

ICPC

게시판에 있는 반례들은 다 만족시켰는데

minripex 3년 전 0

1207koo 3년 전 1

minripex 3년 전 0

minripex 3년 전 0

1207koo 3년 전 0

minripex 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말