Life Engineering
[BOJ 1182] 부분수열의 합 (Python3) 본문
from itertools import combinations
N, S=map(int, input().split())
L=list(map(int, input().split()))
count=0
for i in range(N):
cb=list(combinations(L,i+1))
for item in cb:
if sum(item)==S:
count+=1
print(count)
combination을 이용해 부분수열의 원소의 개수가 1개일 때, 2개일 때, ... , n개일 때로 나누어 합이 S면 count+=1 해준다.
재귀로도 풀 수 있다는 사실..
#include <iostream>
using namespace std;
int N, S;
const int MAX = 20;
int arr[MAX];
int cnt;
void find(int sum, int n)
{
if (n == N) { // n이 N이 된다면 S와 같은지 보고 같다면 cnt 를 1 더해준다.
if (sum == S)
cnt++;
return;
}
find(sum + arr[n], n + 1); // 숫자를 더해주고 n을 1 늘린다.
find(sum, n + 1); // 숫자를 더하지 않고 n을 1늘린다.
}
int main()
{
cin >> N >> S;
for (int i = 0; i < N; ++i)
{
cin >> arr[i];
}
find(0, 0);
if (S == 0) // S가 0일시 끝까지 아무것도 더하지않아도 경우의수가 추가 되기 때문에 1을 빼줬다.
cout << cnt - 1 << endl;
else
cout << cnt << endl;
return 0;
}
'Problem Solving' 카테고리의 다른 글
[BOJ 15686] 치킨 배달 (Python3) (0) | 2021.02.15 |
---|---|
[BOJ 14502] 연구소 (Python3) (0) | 2021.02.15 |
[BOJ 14889] 스타트와 링크(Python3) (0) | 2021.02.14 |
[BOJ 9205] 맥주 마시면서 걸어가기 (Python3) (0) | 2021.02.14 |
[BOJ 2467] 용액(Python) (0) | 2021.02.13 |