[백트랙킹]백준1182번 부분수열의 합

백준1182

풀이를 아무리 봐도 이해가 되지 않던 문제였다.

이유는 내가 수학적인 이해가 너무 부족했기 때문이다.

부분 수열

위키백과, 우리 모두의 백과사전.

둘러보기로 가기

검색하러 가기

수학에서, 부분 수열(部分數列, 영어: subsequence) 또는 부분열(部分列)은 주어진 수열의 일부 항을 원래 순서대로 나열하여 얻을 수 있는 수열이다.

즉, 원래 수열의 순서를 깨면 안된다.

이걸 몰라서 일반적인 백트랙킹처럼 모든 조합을 다 구하고 같은 set들을 걸러내는 등 예외처리를 하고 있었다. 아무리 생각해도 이건 아니다 싶어서 검색을 해봐서 겨우 알게 되었다.

일반적인 백트랙킹에서는 현재 상태에서 내가 어디로 가야 하는지를 정하며 갈 수 있는 곳들을 따로 정의하기 위해 boolean 배열을 따로 사용하곤 한다.

하지만 이번 문제처럼 원래 수열의 순서를 깨면 안된다면, 선택지는 무조건 나보다 뒤에 있는 것들이다.

현재 위치에서 갈 수 있는 곳은 입력으로 받은 수열에서 현재 위치보다 뒤에 있는 곳 밖에 없다.

따라서 나보다 뒤에 있는 곳, 즉 내 바로 뒤 수를 건너 뛴 상태로 그 다음 수들을 더할지

내 바로 뒤 숫자를 더하고 그 다음 수들을 더해갈 지에 대한 모든 경우의 수를 구하면 되는 문제이다.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
int N,S;
vector<int> num;
bool isUsed[200001];
int sum = 0;
int cnt = 0;

void btk(int sum,int index){
    // 만약 끝까지 다 더한거라면
    if(index == N) return;
    // 만약 누적 합이랑 나랑 더해서 S 라면
    if(sum + num[index]==S) cnt++;
    
    //나를 건너 뛰고 갈 지 
    btk(sum,index+1);
    btk(sum+num[index],index+1);

}

int main(){
   cin >> N >> S;
   for(int i=0;i<N;i++){
       int temp;
       cin >> temp;
       num.push_back(temp);
   } 

    btk(0,0);
    cout << cnt;
}