[백준] 1182 - 부분수열의 합 (C++)

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

N개의 정수로 이뤄진 수열이 있을 때, 크기가 양수인 부분수열 중 그 수열의 원소를 모두 더한 값이 S가 되는 부분수열의 개수를 구하는 문제다.

 

---

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

ex. 가능한 시간 복잡도, 알고리즘 선택

입출력 제한

• 1 ≤ N ≤ 20
• |S| ≤ 1,000,000 (주어지는 정수의 절댓값은 100,000을 넘지 않음)

 

만들 수 있는 모든 부분수열의 개수는 2²⁰ = 1,048,576개다. 부분수열마다 모든 원소의 합을 구하는 방식은 불가능하고, 백트래킹 알고리즘을 사용해야 할 것 같다.

또, 모든 정수를 다 더하더라도 int 범위를 넘지 않으므로 int까지만 사용해도 된다.

 

---

코드 설계하기

위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!

- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지

1. N, S 입력 받기
2. 부분합을 저장할 배열을 선언하고 N개의 정수를 입력받을 때마다 부분합 배열에 저장
3. 부분합끼리의 차를 통해 값이 S가 나오는 경우, 정답 개수에 추가
4. 정답 개수 출력

1. N, S 입력 받기
2. 배열에 정수 입력 받기
3. 백트래킹으로 원소를 고르고 빼면서 합이 S와 같다면 정답 개수에 더하기
4. 정답 개수 출력

 

---

시도 회차 수정 사항 (Optional)

- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!

1회차

• 부분합 알고리즘 -> 부분수열은 N개의 원소 중 임의로 골라서 만들어지기 때문에 사용할 수 없음
• 백트래킹 알고리즘 사용

 

---

정답 코드

#include <iostream>
using namespace std;

int n,s,ans,arr[21];

void dfs(int cnt, int dep, int sum) {
    if (dep==n) {
        if (cnt>0 && sum==s)
            ans++;
        return;
    }
    dfs(cnt+1, dep+1, sum+arr[dep]);
    dfs(cnt, dep+1, sum);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> s;
    for (int i=0; i<n; i++)
        cin >> arr[i];
    
    dfs(0,0,0);

    cout << ans;
}