[BOJ/백준] 1182 부분수열의 합

● [문제번호 1182] 부분수열의 합

https://www.acmicpc.net/problem/1182

1182번: 부분수열의 합

 

● 알아야 할 것

: DFS

: 재귀

 

● 풀이 과정

: 구현을 계속 해도 '시간 초과', '틀렸습니다' 를 반복해서
문제를 다르게 이해했나 생각해서 구글링을 했다.

 

: {기존 배열에서 1개라도 선택했는가} + {부분수열의 원소 총합 = S} 인 경우

부분 수열의 갯수(cnt)를 올린다.

 

그리고 index가 기존 수열의 끝까지 간 경우 더이상 진행하지 않고 반환한다.

 

● 주의 할 것

: 문제에서 말하는 부분수열은

1. 기존 수열에서 연속될 필요X

→ 예를 들어, 입력이

6 3

-3 -2 -1 0 2 3

인 경우 출력은 4이다.

(3) (0 3) (-2 2 3) (-2 0 2 3)

 

2. 기존 수열에 동일한 원소가 있는 경우, 부분 수열 중복 가능

→ 예를 들어, 입력이

6 2

1 1 1 1 1 1

인 경우 출력은 15이다.

 

3. 기존 수열에서 부분 수열의 원소를 뽑는 순서는 달라도 된다.

→ 부분 수열 함수를 호출하기 전,

main 함수에서 입력된 기존 수열을 sort해도 결과에 영향을 미치지 않는다.

(미리 정렬해도 됨)

 

결국 조합을 말하는 것 같다.

 

● 참고 할 것

: 풀이 과정 이해

https://ijsilver.tistory.com/43

 

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// N개 수열 입력
int sequence[21];
int N, S, cnt;

// 부분 수열 갯수 세기
void subsequence(int index, int total)
{
    // {크기가 양수인 부분 수열} + {수열의 원소를 다 더한 값이 S}
    // 여기서 return을 하면 안됨
    // → 그 뒤에 원소들을 더해도 S가 나올 수 있기 때문
    if(index != 0 && total == S)
        cnt++;
    
    // 수열 끝까지 간 경우
    if(index == N)
        return ;
    
    // 조합을 위해 반복문 초기값은 index부터
    for(int i = index; i < N; i++)
        subsequence(i + 1, total + sequence[i]);
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N >> S;
    
    // 수열 저장
    for(int n = 0; n < N; n++)
        cin >> sequence[n];
    
    // index : 0부터 / 총합 : 0
    subsequence(0, 0);
    
    cout << cnt;
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 2/2] - [540 - 브루트 포스 - 비트마스크] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	11723	집합	https://pirateturtle.tistory.com/265
2	1182	부분수열의 합	https://pirateturtle.tistory.com/266
3	14889	스타트와 링크	https://pirateturtle.tistory.com/267
4	14391	종이 조각	https://pirateturtle.tistory.com/268