60. 합이 같은 부분집합(DFS : 아마존 인터뷰)

it 취업을위한알고리즘문제풀이

문제

60. 합이 같은 부분집합(DFS : 아마존 인터뷰)
    N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때
    두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES"를 출력하고, 그렇지 않으면
    ”NO"를 출력하는 프로그램을 작성하세요.
    예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이
    16으로 같은 경우가 존재하는 것을 알 수 있다.
    ▣ 입력설명
    첫 번째 줄에 자연수 N(1<=N<=10)이 주어집니다.
    두 번째 줄에 집합의 원소 N개가 주어진다. 각 원소는 중복되지 않는다.
    ▣ 출력설명
    첫 번째 줄에 “YES" 또는 ”NO"를 출력한다.
    ▣ 입력예제 1
    6
    1 3 5 6 7 10
    ▣ 출력예제 1
    YES

코드

//60. 합이 같은 부분집합(DFS : 아마존 인터뷰)
#include <stdio.h>
#include <stdlib.h>
int n;
bool flag = 0;
int num[10];
int subnum[10];
int sum1;
int sum2;
//부분집합 구하기
void dfs(int level) {
    if (flag == true) return;
    if (level == n) {

        //부분집합 누적합 구하기
        sum1 = sum2 = 0;
        for (int i = 0; i < n; ++i) {
            if (subnum[i] == true) {
                sum1 += num[i];
            }
            else {
                sum2 += num[i];
            }
        }

        if (sum1 == sum2) {
            flag = 1;
        }
        return;
    }

    subnum[level] = true;
    dfs(level + 1);

    subnum[level] = false;
    dfs(level + 1);

}

int main() {
    //freopen("input.txt", "rt", stdin);
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &num[i]);
    }
    //부분집합 구하기
    dfs(0);

    if (flag == 1) {
        printf("YES\n");
        return 0;
    }

    printf("NO\n");
    return 0;
}

문제해결방법1

• 깊이 우선 탐색(DFS)로 해결 했다.
• 2진트리 형태의 깊이우선탐색으로 좌측에 있는 트리에는 현재 depth값과 같은 index의 요소를 부분집합에 포함시키도록 ture값을 주고 우측 트리에 있는 트리에는 현재 depth값과 같은 index의 요소를 부분집합에 포함시키도록 false값을 주면서 깊이우선탐색을 수행했다.
• depth가 집합의 주어진 원소의 개수 n에 도달하면 깊이우선탐색을 종료하면서 문제의 주어진 부분집합의 sum값을 구한다.
  • sum 값을 구하는 알고리즘은 true값을 준 인덱스의 요소의 값들을 누적하여 더하고 false값으로 남아있는 인덱스의 요소들을 누적해서 더하고 두 값을 비교하여 같다면 flag값을 true로하여 dfs함수 return이 끝났을 때 flag값이 true 이면 YES를 출력하도록 한다. 아니면 NO를 출력한다.
  • 이때 다음 dfs함수 호출에서 이미 flag값이 true라면 더 이상 계산할 필요가 없기 때문에 return하는 부분을 추가시켜 프로그램의 효율성을 증가시킨다.

문제해결방법1

• 입력받으면서 문제의 주어진 집합의 원소들의 total값을 구한다.
• 같은 방식이지만 sum 값을 같이 매개변수로 주어 depth마다 현재 depth값에 해당하는 index의 요소값을 누적하여 다음 dfs 함수의 sum매개변수에 전달하여 누적값을 구하는 코드도 구현하였다.
• 트리의 우측에서 현재 depth에 해당하는 index의 요소값을 포함시키고 싶지 않을 때는 그냥 현재 depth에서의 sum만 다음 함수의 sum매개변수에 전달하면 된다.
• 그리고 나머지 부분집합에 대해서는 집합전체의 합에서 현재 sum값을 total값에서 빼주어 나머지 부분집합의 합를 구한다.
• 이때 두 값이 같다면 위에서와 마찬가지고 flag값을 true로 하며 YES값을 출력하도록 하고 false라면 NO를 출력하도록 한다.