https://www.acmicpc.net/problem/1182
1182번: 부분수열의 합
첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.
www.acmicpc.net
📌 작성한 코드
// 1182
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Silver/test.txt";
const input = fs.readFileSync(filePath).toString().trim().split("\n");
const [n, s] = input[0].split(" ").map(Number);
const list = input[1].split(" ").map(Number);
let answer = 0;
const recursion = (at, sum) => {
if (at === n) return;
sum += list[at];
if (sum === s) {
answer++;
}
recursion(at + 1, sum);
recursion(at + 1, sum - list[at]);
};
recursion(0, 0);
console.log(answer);
📌 풀이
부분 수열 : 주어진 수열의 일부 항을 원래 순서대로 나열하여 얻을 수 있는 수열
- 원래 수열이 [1,2,3,4,5]라고 했을 때 [1,2,3], [1,2,5]와 같이 일부를 제외하고도 순서가 똑같은 수열을 말한다.
- 부분 집합과 다른 점은 순서를 지켜야한다는 것이고, 중간의 일부를 제외한 것도 부분 수열이니까 주의해야 한다.
매 단계에서 해당 숫자를 더해서 만든 수열과 해당 숫자를 더하지 않은 수열 두가지의 부분에 대한 재귀를 실행한다.
const recursion = (at, sum) => {
if (at === n) return;
sum += list[at]; // 수열의 해당 위치 숫자 더하기
if (sum === s) { // 합이 s면 답에 추가
answer++;
}
recursion(at + 1, sum); // 현재 숫자를 더한 값에서 재귀함수 호출
recursion(at + 1, sum - list[at]); // 현재 숫자를 더하지 않은 값에서 재귀함수 호출
};
✅ 성공

'알고리즘 > 백준' 카테고리의 다른 글
| [JavaScript/백트래킹] 백준 실버 1 : 14889 - 스타트와 링크 (2) | 2024.02.08 |
|---|---|
| [JavaScript/백트래킹] 백준 골드 4 : 9663 - N-Queen (0) | 2024.02.08 |
| [JavaScript/백트래킹] 백준 골드 5 : 16987 - 계란으로 계란치기 (1) | 2024.02.08 |
| [JavaScript/백트래킹] 백준 골드 5 : 1759 - 암호 만들기 (1) | 2024.02.04 |
| [JavaScript/백트래킹] 백준 실버 2 : 6603 - 로또 (0) | 2024.02.04 |