인프런 커뮤니티 질문&답변

안녕하세요 선생님!

항상 좋은 강의 감사히 잘 듣고 있습니다.

이번 문제에서 제 코드로는 4번 문제가 계속 틀렸다고 나와서 선생님 코드 그대로 따라했는데도 4번 문제가 틀렸다고 되더라구요... 채점기 output이 잘못된건지 제가 짠 코드가 잘못된건지 확인 부탁드립니다...!

1. 제 코드

   #include <stdio.h>
   #include <cmath>
   
   int n;
   int a[11];
   int b[100];
   int c[1025];
   int sum;
   int idx = 1;
   
   void DFS(int x)
   {
   	if(x == n+1)
   	{
   		sum = 0;
   		for(int i = 1; i <= n; i++)
   			if(b[a[i]] == 1)
   				sum += a[i];
   		c[idx++] = sum;
   	}
   	else
   	{
   		b[a[x]] = 1;
   		DFS(x+1);
   		b[a[x]] = 0;
   		DFS(x+1);
   	}
   }
   
   int main()
   {
   	scanf("%d", &n);
   	
   	for(int i = 1; i <= n; i++)
   		scanf("%d", &a[i]);
   	
   	DFS(1);
   	
   	for(int i = 1; i <= pow(2, n); i++)
   	{
   		int temp = c[i];
   		if(temp == 0)
   			continue;
   		for(int j = 1; j <= pow(2, n); j++)
   		{
   			if(i == j)
   				continue;
   			
   			if(temp == c[j])
   			{
   				printf("YES");
   				return 0;
   			}
   		}
   	}
   	
   	printf("NO");
   	return 0;
   }

2. 선생님 코드

#include <stdio.h>

int n;
int a[11];
int total = 0;

bool flag = false;
void DFS(int x, int sum)
{
	if(sum > (total/2)) return;
	if(flag) return;
	if(x == n+1)
	{
		if(sum == (total/2))
		{
			flag = true;
		}
	}
	else
	{
		DFS(x+1, sum+a[x]);
		DFS(x+1, sum);
	}
}

int main()
{
	scanf("%d", &n);
	
	for(int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
		total += a[i];
	}
	
	DFS(1, 0);
	
	if(flag)
		printf("YES");
	else
		printf("NO");
	return 0;
}