[BOJ 1182] 부분수열의 합 (Python3)

www.acmicpc.net/problem/1182

1182번: 부분수열의 합

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;

}

100100e.tistory.com/21