sang ji Choi

작성한 질문수 23

0

안녕하세요^^

재귀함수 안에서 YES, NO를 출력하면 매번 부분집합의 경우가 완성될 때마다 YES, NO가 출력됩니다.

그리고 ch[L] = 1로 체크하고 DFS(L+1, sum+a[L])와 같이 해야 합니다.

개선된 코드를 넣어드립니다. 분석해보세요.

#include<bits/stdc++.h>
using namespace std;
int n, total = 0;
int ch[11];
int a[11];
int flag = 0;
void DFS(int L, int sum)
{
    if(flag) return;
    if (L == n + 1)
    {
    	cout<<sum<<" "<< total - sum<<endl;
        if((total - sum) == sum) flag = 1;
    }
    else
    {
        ch[L] = 1;
        DFS(L+1, sum + a[L]);
        ch[L] = 0;
        DFS(L+1, sum);
    }
    
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        total = total + a[i];
    }
    DFS(1, 0); //시작점 합
    if(flag) cout<<"YES";
    else cout<<"NO";
}

0

안녕하세요, 인프런 AI 인턴이에요.

코드를 보면서 문제점을 찾을 때, 원하는 결과가 얻어지지 않는 경우일 수도 있으니 문제에서 요구하는 결과와 비교해보는 것도 중요합니다.

제가 보았을 때, 오타는 없는 것 같지만 다음과 같은 문제점이 있을 수 있습니다.

1. DFS 함수에서 sum 전달 값에 동일 변수(sum)를 이용하여 누적시키고 있어 잘못된 결과를 만들 수 있습니다. sum이라는 변수를 다른 변수명으로 변경하여 사용하십시오.

2. DFS 함수에서 L+1을 ch[L+1]로 변경하여 처리합니다. 이 부분을 ch[L]=1, ch[L]=0 으로 변경하여 처리하시면 됩니다.

3. 탈출 조건인 L == n+1 일 때 결과 출력을 누락하고 있으니 결과 출력을 추가하면 됩니다.

다음은 수정된 코드입니다.

#include
#include
using namespace std;

int n, tatal = 0;
int ch[11];
int a[11];

void DFS(int L, int sum)
{
int sum2 = 0;
if (L == n + 1)
{
for (int i = 1; i <= n; i++)
{
if (ch[i] == 1)
{
sum = sum + a[i];
}
else if(ch[i] == 0)
{
sum2 = sum2 + a[i];
}
}
if (tatal - sum == sum2)
{
cout << “YES” << endl;
exit(0);
}
return;
}
else
{
ch[L] = 1;
DFS(L+1, sum);
ch[L] = 0;
DFS(L+1, sum + a[L]);
}
}

int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
tatal = tatal + a[i];
}
DFS(1, 0); //시작점 합
cout << “NO” << endl;
return 0;
}

이상입니다. 참고하시길 바랍니다. :)