[백준] 1182

부분수열의 합

문제

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

출력

첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

풀이

let ans = 0;
let n;
let s;

const recurSeq = (input, k, sum) => {
  if (k === n && sum === s) ans++;
  if (k === n) return;
  recurSeq(input, k + 1, sum + input[k]);
  recurSeq(input, k + 1, sum);
};

const seq = () => {
  let input = require("fs")
    .readFileSync("/dev/stdin")
    .toString()
    .trim()
    .split("\n")
    .map((n) => n.split(" ").map(Number));
  n = input[0][0];
  s = input[0][1];
  recurSeq(input[1], 0, 0);
  console.log(!s ? ans - 1 : ans);
};

seq();

반성회

첨에 혼자 힘으로 풀겠다고 끙끙 싸맸는데 실제 풀이과정은 되게 쉬워서.... 어이가 없었던 기억이

• n, s : 문제에서 주어지는 N과 S (N은 수열의 길이, S는 얻어내고자 하는 수열의 합)
• input[1] : 테스트케이스에 해당하는 수열
  • input[0]과 input[1]은 개행 (\n) 을 기준으로 잘렸으므로, 두 번째 줄에 주어지는 수열이 input[1]에 저장된다
  • input[0]과 input[1] 모두 내부의 숫자들은 공백 ( ``) 을 기준으로 구분되므로 공백 기준으로 한번 더 split하고, Number 타입으로 매핑했다
• ans : 전역 범위에 존재하는, 합이 S임을 만족하는 수열의 개수
• sum : 현재 계산하는 부분수열의 총합

재귀 진행 순서

1. k는 자리수를 나타내고, 0번째 자리부터 계산하므로 recurSeq의 인자 k는 0으로 세팅하여 시작
2. ans의 증가 조건은 k가 n이고 sum이 s일 때이다
   • k는 원본 수열의 k번째 자리를 sum에 더했는지 여부와 관계없이 다음 재귀로 넘어갈 때 증가한다
   • 수열의 모든 수를 탐색했을 경우 k는 n - 1이 되며 그 상태에서 k에 1을 더해 다음 재귀로 넘어갈 경우 더이상 탐색할 수 있는 수가 없어 sum과 s를 비교하고 ans의 증가 여부를 결정한다
3. recurSeq의 탈출조건은 k가 n일 때이다
   • n은 수열의 총 숫자의 개수이므로, 부분수열의 자리수는 n을 절대 넘을 수 없다
   • 또한 수열의 k번째 수를 더하지 않는 경우에도 다음 재귀로 넘어갈 때 k가 증가하므로, k는 무조건 n에 도달한다
4. k가 n이 아닐 경우, 재귀에 들어간다
   • 한 재귀 레벨마다 두 번 분기하는데, 첫 번째는 sum에 input[k] (수열의 k번째 수) 를 더하는 경우이고, 두 번째는 더하지 않는 경우이다
   • sum에 input[k]를 더하는 경우는 계산하고자 하는 부분수열이 input[k]를 포함하는 경우이며, 따라서 다음 재귀로 넘어갈 때 sum에 sum + input[k]를 대입하고, k에 k + 1을 대입한다
   • sum에 input[k]를 더하지 않는 경우는 부분수열이 input[k]를 포함하지 않는 경우이므로, 수열의 다음 수에 대해서 계산하기 위해 k에 1을 더하여 재귀에 들어간다
5. 모든 재귀를 빠져나와 recurSeq을 종료하고 seq 함수로 돌아왔다는 것은 모든 경우의 수를 탐색하여 가능한 부분수열과 그 합을 전부 찾아내었고, 그 중 합이 s인 경우의 개수를 전부 세었다는 뜻이므로, ans를 출력한다