백준 #1182 부분 수열의 합

난이도 : 실버2
소요시간 :  58분
사용한 풀이법 : 백트래킹

---

풀이 과정

1. 현재 원소 위치와 총합을 매개변수로 하는 func()정의
2. 현위치 변수가 n과 같고, 총합이 s와 같은 경우에 카운트 후 리턴
3. 조건 미 충족 시, func() 재귀
4. 재귀는 다음 위치의 수를 더하는 경우와, 더하지 않는 경우 두가지로 진행
5. S가 0일 때, 모두 더하지 않은 경우를 카운트에서 제외시켜야 함.

작성 코드

#include <iostream>
using namespace std;

int 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+arr[cur]);
  func(cur+1, tot);
}
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);
  if(s == 0) cnt--;
  cout << cnt;
}

 

 

피드백

이건 재귀를 써야하는 문제다.. 생각은 들지만 암만 떠올려도 안되서 결국 정답 코드 염탐했다.
근데 그 마저도 이해하는데 10분은 걸린 내 자신이 싫지만 그래도 뭐 계속 해야지 어쩌겠나..
다음 문제는 스스로 풀어보자.