글 읽기 - 이 문제를 백트래킹 방법으로 풀면 안되고 dp로 풀어야되는 이유가 무엇인가요?

ktjs7252 1년 전 0

이 문제를 보고 dp로 풀어야 된다는 생각을 하지못하고 백트래킹이라고 생각했습니다.

문제를 보고 dp로 풀어야된다고 생각은 어떤 부분을 통해 할 수 있나요?

백트래킹이 안되는 이유도 알려주시면 감사하겠슴다 ! ㅠㅠ

백트래킹은 밑에와 같은 방식으로 할 거 같아요!

void solve(int counting,int sum)
{
	if(counting==m && sum==n )
	{
		answer++;
		return;
	}
	if(counting>m|| sum>n)
	{
		return;
	}
	
	for(int i=0;i<=n;i++)
	{
		if(visited[i]==0)
		{
			visited[i]=1;
			solve(counting+1,sum+i);
			visited[i]=0;
		}
	}

} 

djs100201 1년 전 0

시간복잡도를 한번 계산해보세용

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

문제

문제

출처

ICPC

이 문제를 백트래킹 방법으로 풀면 안되고 dp로 풀어야되는 이유가 무엇인가요?

ktjs7252 1년 전 0

djs100201 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말