19년 9월 1주차 : 환상의 조합

1. 문제 - 난이도 ★★

팀원들의 능력치가 주어졌을 때 홍현이의 능력을 포함한 그 합이 S가 되게하는 환상의 조합을 구하라.

 

2. 입력

첫번째 줄에는 사람 수 N과 팀원들의 능력합 S가 주어진다

두번째 줄부터 N명의 사람들의 능력치가 주어진다. 첫번째로 주어지는 능력은 홍현이의 능력이다.  

 

3. 출력

최고의 팀을 만들 수 있는 경우의 수 출력, 팀원은 최소 1명 이상이어야 한다. 즉, 홍현이 혼자 팀을 구성할 수 있다..

 

4. 알고리즘 : 완전 탐색

홍현이를 포함하는 부분집합의 합이 S가 되는 경우의 수를 찾는 문제이다. 집합 A의 크기가 n일 때 공집합을 포함한 부분집합의 개수는 2^n개이다. 따라서 문제는 O(2^N)시간안에 풀 수 있다. 

 

완전 탐색은 두가지 방법이 있다.

1. 재귀 함수

2. 비트 마스크

 

재귀 함수를 이용해서 풀어보자.

 

5. 코드

# 입력처리
N, S = map(int, input().split())
status = list(map(int, input().split()))

count = 0 # 경우의 수 카운팅 변수

def best(v, cur_sum):
    global count
    if v == N: # 모든 팀원을 체크했을 경우
        count += (cur_sum == S) # 현재 부분집합의 합이 S와 같으면 +1
        return
    best(v+1, cur_sum) # 다음 사람을 포함하지 않는 부분집합
    best(v+1, cur_sum+status[v]) # 다음 사람을 포함하는 부분집합

best(1, status[0]) # 홍현이를 포함한 부분집합에서 시작
print(count)