백준, BOJ, 1182번 C++ [CPP] ★★

//첫번째 풀이 2021.05.26

//두번째 풀이 2022.02.08

 

이 문제도 백트래킹이지만

조금 꼬아서 냈다.

출력을 조금 더 어렵게했다.

 

 

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

1182번: 부분수열의 합

---

 

우선 내가 접근했던 틀린 풀이부터 보자

#include<iostream>
#include<vector>

using namespace std;

void init() {
    ios::sync_with_stdio(0);
    cin.tie(0);

}

int a, b; // a주어진 개수, b 목표합
int cnt = 0;

int arr[21]; // 선택 체크 배열
vector<int> V; // 선택한 숫자들;
int num[21]; // 입력받은 숫자들

//k는 현재 선택한 개수, n는 부분순열의 크기  
void func(int k, int n) {
    //n개 선택했으면
    if (k == n) {
        int sum = 0;
        //선택한 숫자들의 합 구하기
        for (int n : V) {
            sum += n;
        }
        //합이 같다면
        if (sum == b) {
            cnt++;
            return;
        }
        return;
    }

    //모든 숫자에 탐색
    for (int j = 0; j<a; j++) {
        V.empty();
        if (arr[j] == 0) {
            arr[j] = 1;
            V.push_back(num[j]);
            func(k + 1, n);
            V.pop_back();
            arr[j] = 0;
        }
    }
}

//위 함수로 문제 풀이시 중복됨 - > -3, -2, 5로 6개의 0을 만들 수 있음.



int main() {
    cin >> a >> b;
    for (int i = 0; i<a; i++) {
        cin >> num[i];
    }

    for (int j = 1; j <= a; j++) {
        func(0, j);
    }

    cout << cnt;
}

 

신난다 코딩 잘된다 하고 짰지만 ㅋㅋㅋㅋㅋ

그렇다. 중복되어서 세어서 답이 틀리게 나온다..

그렇다면 어떻게 해야할까..? 

 

그냥... 이렇게 하는 방법이 있다.

매순간 탐색할 때마다 숫자를 더할지 말지 체크를 하는 것이다. 

만약 5개를 탐색한다면 32개가 나오겠지 ?? 2^5 = 32 니까?

 

예를 들어 3개면.. 이렇게

바킹독

 

더하면 오른쪽 트리로 확장

아니면 왼쪽 트리로 확장.

** 맨 왼쪽 아래 노드 => 모든 수 내비둠,  맨 오른쪽 아래 노드  => 모든 수 더함

 

 

 

이를 이용해서 아래와 같은 코드를 짜면 된다.

#include<iostream>
#include<vector>

using namespace std;

int n, s; // n이 주어질 수열의 총 개수, s 목표 합
int arr[30]; // 적당한 크기의 배열
int cnt = 0; // 숫자 세기


void func(int cur, int tot){
  if(cur == n){
    if(tot == s) cnt++;
    return;
  }
  
  func(cur+1, tot); // 현재 수열은 더하지 않기로 하였다.
  func(cur+1, tot+arr[cur]); // 현재 수열은 더하기로 하였다.
    
  //사실 그냥 재귀느낌이 강하게 들지..? 
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
    
  cin >> n >> s;
    
  for(int i = 0; i < n; i++)
    cin >> arr[i];
    
  func(0, 0);
    
  //아무것도 안 더한 것은 크기가 0이므로 제외함
  if(s == 0) cnt--;
  cout << cnt;
}

 

하지만 느낌이 기존의 백트래킹과 조금 다른 느낌이지..? 

그래서 내가 위처럼 잘못풀어서 틀렸고..?

아무튼.. 이렇게도 풀 수 있는 유연한 사고를 가진다면.. 좋겠는데

난 아직 멀었다.

 

---

#두 번째 풀이

#include <bits/stdc++.h>

using namespace std;
int  N, S;
int num[20];

int ans;


void func(int cnt, int val){
    if(cnt == N){
        if(val == S)
            ans++;
        return;
    }
    
    for(int i = 0; i<2; i++){
        if(i == 1){
            func(cnt+1, val+num[cnt]);
        }else if(i == 0){
            func(cnt+1, val);
        }
    }
    
}

int main(){
    cin >> N >> S;
    
    for(int i = 0; i<N; i++){
        cin >> num[i];
    }
    
    func(0,0);
    
    if(S == 0)
        ans--;
    cout << ans << '\n';
    
    
    
    return 0;
}

 

if문이 없어도 되는데.. 강박인가보다