[BEAKJOON] 1182_부분집합의 합_C언어

https://www.acmicpc.net/problem/1182

풀이

부분집합의 합을 구하여 입력된 S와 같은 부분집합의 개수를 출력하는 문제이다.

여기서 내가 생각하는 중요한 점은 두 가지이다.

1. 부분집합을 구하는 방법

2. 부분집합을 구하는 중간에 S와 같다고 개수를 카운트하면 안 된다는 것이다.

설명

부분집합을 구하는 방법은 아래 그림과 같이 그래프를 그려 표현할 수 있다.

그림은 이상하지만...위의 그림처럼 입력된 배열의 값들을 사용할지 안 할지를 구분해가면서 트리의 끝에 가서 부분집합의 합을 구하여야 된다는 것이다.

마지막에 부분집합의 구해야되는 이유는 만약 N이 5, S가 3이며 입력되는 수들이 1 1 2 -1 1을 예로들면

N=5, S=3, arr[5]={1,1,2,-1,1}

3=arr[0]+arr[2]=arr[1]+arr[2]가 답이라 여기서 카운트를 해버리면 틀리게된다.

그 이뉴는 3=arr[0]+arr[2]+arr[3]+arr[4]=arr[1]+arr[2]+arr[3]+arr[4]도 답이기 때문에 트리의 끝까지 가서 집합의 합을 구하여야 된다는 것이다.

아래는 N=5, S=3, arr[5]={1,1,2,-1,1}의 예이다. 부분집합들의 합이 3인 집합들을 출력한 것이다.

제출한 코드

처음 제출한 코드에서 num++해준 코드에 반복문과 조건문을 사용하면 위의 사진과 같이

조건을 만족하는 부분집합을들 출력할 수 있다. 

 
//처음 답안으로 제출한 코드
#include <stdio.h>
int N, S, arr[20], num,visit[20],k;
 
void check(int n)
{
    int total = 0; int flag = 0;
    if (n == N)
    {
        for (int i = 0; i < n; i++)
        {
            if (visit[i])
            {
                flag = 1;
                total += arr[i];
            }
        }
        if (total == S&&flag==1)
        {
            num++;
        }
        return;
    }
 
    visit[n] = 1;
    check(n + 1);
 
    visit[n] = 0;
    check(n + 1);
}
 
int main()
{
    scanf("%d %d",&N, &S);
    for (int i = 0; i < N; i++)
        scanf("%d",&arr[i]);
 
    check(0);
 
    printf("%d",num);
    return 0;
}
 
//수정하여 제출한 코드
#include <stdio.h>
int N, S, arr[20], num;
 
void check(int n,int total)
{
    if (n > N) return;
    if (n == N&&total==S)
    {
        num++;
        return;
    }
    check(n + 1,total+arr[n]);
    check(n + 1,total);
}
 
int main()
{
    scanf("%d %d",&N, &S);
    for (int i = 0; i < N; i++)
        scanf("%d",&arr[i]);
 
    check(0,0);
    if (S == 0) num--; //S가0이면 공집합도 해로 카운트해서 정답에서 -1을 해주었다.
    printf("%d",num);
    return 0;
}