BOJ1182_부분집합의 합의 갯수

부분 집합의 합 갯수 문제는 여러 방법으로 풀 수 있는데, 이번 포스팅에서는 

Back Tracking 방법과 비트마스크 방법으로 풀어보겠습니다.

보통 부분집합의 합을 구하는 것은 비트마스크 방법으로 푸는 것이 가장 좋지만, 재귀 함수를 이용한 Back Tracking 방법을

적용해서도 풀어보려 합니다.

우선 비트마스크 방법을 사용해서 풀어보겠습니다.

비트 마스크의 기본 공식부터 체크하고 가겠습니다.

---

A << B 

: A * 2^B

A >> B

: A / 2^B

A & ( 1 << 2 ) 

: A에서 2가 있는지를 확인

A | ( 1 << 2 )

: A에다가 2를 추가

A & ~( 1 << 2 ) 

: A에서 2를 제거하는 것

A ^ ( 1 << 2 )

: A에서 2를 토글 ( 2에서 0을 1로 , 1을 0으로 )

---

이 개념을 가지고 가면 됩니다.

코드는 간단합니다.

공집합을 제외한 부분집합의 갯수는 2^N - 1 입니다.  이 정도는 수학 공식으로 알 수 있기 때문에 별도로 설명하지 않겠습니다.

따라서 1부터 2^N까지 i를 토대로 한 반복문을 돌리면서 0부터 N-1까지의 값이 i에 존재하는지 여부를 파악하면 됩니다.

존재하면 해당 인덱스를 입력한 배열의 인덱스로 넣어서 값을 구합니다.

이를 sum에 추가하고 기존에 문제대로 S값과 같을 경우 카운트를 증가하면 됩니다.

int cnt = 0; 

for(int i=1;i<(1<<N);i++){

int sum = 0;

for(int j=0;j<N;j++){

if( i & ( 1 << j )) {

sum += input[j]; 

}

}

if( S == sum)

cnt += 1;

}

이게 끝입니다.

이게 핵심 코드이자 끝입니다. 

나머지는 질문대로 진행하면 됩니다.

전체 코드는 다음과 같습니다. 

---

import java.util.Scanner;

public class 부분집합의합_비트마스크 {

private static Scanner scan;

private static int[] input;

public static void main(String[] args) {

// TODO Auto-generated method stub

scan = new Scanner(System.in);

int N = scan.nextInt(); // 횟수

int S = scan.nextInt(); // 합계

input = new int[N];

for (int i = 0; i < N; i++)

input[i] = scan.nextInt();

int ans = 0;

// 2^N == ( 1 << N )

for (int i = 1; i < (1 << N); i++) {

int sum = 0;

for (int j = 0; j < N; j++) {

// 존재할 경우

if ((i & (1 << j)) != 0) {

sum += input[j];

}

}

if (S == sum)

ans += 1;

}

System.out.println(ans);

}

}

---

이번에는 Back Tracking을 활용한 재귀함수로 풀어보겠습니다.

~~한 횟수 문제일 경우 , 기존에 배운대로 go() 함수를 만드는 것을 바로 생각해야 합니다.

go() 함수의 인자로는 첫 번째 인자에는 {배열,스택,큐,벡터,리스트} 등이 들어갈 것이고, 두 번째 인자는 보통 boolean 배열 , (boolean 함수가 없을 경우)

이 들어갑니다. (해당 위치에 갈 수 있는지 여부 체크하기 위함)

(--> 만약 boolean이 쓰였다면, Back Tracking 방식을 사용할 경우 노드 이동시에 true를 주고 다시 재귀로 부른 다음에는 노드를 다시 돌아와서 이동하는

것이기 때문에 false로 체크해야 합니다. )

세 번째 인자로는 첫 번째 인자로 받은 배열값이 이동할 index가 들어가야하며 네 번째는 얼마만큼의 횟수 인지 체크하는 count가 필요합니다.

(이 부분집합의 합 카운트 문제에서는 본 함수의 count가 쓰이지 않습니다. 본 count는 함수 go가 얼마나 반복되는지 체크하는 함수이기 때문입니다.)

마지막으로 5번 째 인자로는 합계를 나타내는 sum입니다. 

이는 들어가도 되고 안들어가도 되지만, 합계와 관련된 문제가 나올 경우 들어가는 편입니다.

재귀 함수는 그 다음으로 중요한 것이 종료조건과 정답조건을 알아내는 것입니다.

인자로 받은 배열이 끝날 때 까지 다 돌면 함수는 종료하게 됩니다.

입력 받은 배열의 요소들의 부분집합의 합을 체크하는 것이기 때문입니다.

이는 종료 조건이자 정답 조건이 되는 조건입니다.

종료 조건은 앞서 전제가 되는 조건 내에서 만약 S가 sum과 다를 경우가 종료 조건이고,

정답 조건은 S와 sum이 같을 경우입니다.

코드는 다음과 같습니다.

private static int go(int[] A, int S , int index , int count , int sum) {

int ans = 0; // cnt 

if( S.length == index ) {

if( S == sum )

return 1;

else

return 0;

}

return go(A,S,index+1,count+1,sum+A[index]) + go(A,S,index+1,count+1,sum); 

}

코드를 분석하면 어떤 내용인지 알 것입니다.

전체 코드는 다음과 같습니다.

---

import java.util.*;

public class 부분집합의합_1182 {

private static Scanner scan;

private static int[] input;

public static void main(String[] args) {

// TODO Auto-generated method stub

scan = new Scanner(System.in);

int N = scan.nextInt();

int S = scan.nextInt();

int index = 0;

input = new int[N];

while(N-->0) {

input[index] = scan.nextInt();

index+=1;

}

int ans = go(input,S,0,0,0);

if(S == 0)

ans -= 1;

System.out.println(ans);

}

private static int go(int[] A, int S, int index, int cnt, int sum) {

if(index == -1)

return -1;

if (A.length == index) {

// 합으로 정한 S값이 다 더한 sum과 같아 버리면 1을 반환 --> 재귀로 합쳐져서 답이 나옴 

if(S == sum) {

return 1;

}else {

return 0; // 종료 조건 : 길이가 같은데 정해놓은 합과 다를 경우 종료 

}

}

return go(A,S,index+1,cnt+1,sum+A[index]) + go(A,S,index+1,cnt+1,sum);

}

}

---