[Algorithm] 백준 - 부분수열의 합 (1182번)

문제

[백준] 부분수열의 합

1182번: 부분수열의 합

 

사용 알고리즘

- 백트래킹(Backtracking)

해결방법

• 문제 자체는, 주어진 수열에서 모든 부분 수열을 확인하면 되는 문제이다.
• 모든 부분 수열을 어떻게 확인할건데 ?? >> 백트래킹을 사용해보자
  • 백트래킹 알고리즘의 핵심은 '해를 찾는 도중에 막히면 되돌아가서 다른 경로를 탐색한다' 이다.
• 문제 예제1을 살펴보면, 다음과 같다
  -- 주어진 수열
  [-7, -3, -2, 5, 8]
  
  -- 호출순서
  1. generateSubsequences([-7, -3, -2, 5, 8], [], 0)
  2. generateSubsequences([-7, -3, -2, 5, 8], [], 1)
  3. generateSubsequences([-7, -3, -2, 5, 8], [], 2)
  4. generateSubsequences([-7, -3, -2, 5, 8], [], 3)
     11. generateSubsequences([-7, -3, -2, 5, 8], [-2], 3)
          12. generateSubsequences([-7, -3, -2, 5, 8], [-2], 4)
                13. generateSubsequences([-7, -3, -2, 5, 8], [-2], 5)
                14. generateSubsequences([-7, -3, -2, 5, 8], [-2, 8], 5) 
          15. generateSubsequences([-7, -3, -2, 5, 8], [-2, 5], 4)
          . . .이하 생략
  5. generateSubsequences([-7, -3, -2, 5, 8], [], 4)
      8. generateSubsequences([-7, -3, -2, 5, 8], [5], 4)
          9. generateSubsequences([-7, -3, -2, 5, 8], [5], 5)
        10. generateSubsequences([-7, -3, -2, 5, 8], [5, 8], 5)
  6. generateSubsequences([-7, -3, -2, 5, 8], [], 5)
      7. generateSubsequences([-7, -3, -2, 5, 8], [8], 5)

 

소스코드

사용언어 : c++

#include <iostream>
#include <vector>
 
using namespace std;
 
int N, S, result;
 
// 백트래킹을 이용하여 부분 수열 생성
void generateSubsequences(vector<int>& sequence, vector<int>& current, int index) {
    if (index == sequence.size()) {
        // 현재 부분 수열 출력
        int sum = 0;
        for (int num : current) {
            sum += num;
        }
        if (current.size() != 0 && sum == S) result++;
        return;
    }
 
    // 현재 원소를 선택하지 않고 다음 원소로 이동
    generateSubsequences(sequence, current, index + 1);
 
    // 현재 원소를 선택하고 다음 원소로 이동
    current.push_back(sequence[index]);
    generateSubsequences(sequence, current, index + 1);
 
    // 백트래킹을 위해 선택한 원소 제거
    current.pop_back();
}
 
int main() {
    vector<int> sequence;
    vector<int> current;
 
    cin >> N >> S;
 
    int num;
    for (int i=0; i<N; i++) {
        cin >> num;
        sequence.push_back(num);
    }
 
    generateSubsequences(sequence, current, 0);
    cout << result << endl;
 
    return 0;
}

 

오늘도 지피티에게 물어보기

 

한줄평

백트래킹 더 공부해야겠다. ㄷㄷ