[JS] 백준 1182번: 부분수열의 합

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

부분 수열이란?

 

주어진 수열에서 일부 항을 원래 순서를 유지한 채 골라낸 새로운 수열을 의미한다. 즉, 원래 수열의 항 중 몇 개를 건너뛰거나 제외하더라도, 남은 항들의 순서가 원래 수열에서의 순서와 같다면 그 수열을 부분 수열이라고 한다. 

 

부분 수열의 특징

• 원래 수열의 순서 유지 : 항을 건너뛰어도 순서는 바뀌지 않는다.
• 항의 개수 제한 없음: 한 항만 남겨도 되고, 원래 수열 전체를 선택해도 된다.
• 반복, 역순 불가: 원래 수열의 항을 반복하거나 순서를 바꿀 수 없다.

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");
const [N, S] = input[0].split(" ").map(Number);
let numbers = input[1].split(" ").map(Number);
let count = 0;

function dfs(idx, sum, arrLen) { // 인덱스, 합, 선택한 원소 개수
  if (idx === N) {
    if (sum === S && arrLen > 0) count++;
    return;
  }

  // 현재 원소를 선택하는 경우
  dfs(idx + 1, sum + numbers[idx], arrLen + 1);
  // 현재 원소를 선택하지 않는 경우
  dfs(idx + 1, sum, arrLen);
}

dfs(0, 0, 0);
console.log(count);

 

✏️ 풀이 방법

간단한 예시

이 문제에서 핵심은 각 원소를 "선택" 하거나 "선택하지 않는" 두 가지 경우로 분기하는 것이라고 한다. 예를 들면  dfs(0,0,0) 으로 시작했다고 하더라도, 0번째 원소인 -1 을 선택하는 경우와 선택하지 않는 경우 둘 다 dfs 탐색을 한다. 

 

✍🏻 느낀점

 

부분 수열을 직접 구현한다고 생각을 하니까 대체 어떻게 해야될지부터 감이 안잡혔던 것 같다. 백트래킹 문제 추천을 받아서 푼 문제인데, 이걸 어떻게 백트래킹으로 하는거지? 싶었다. 이번 문제를 통해 안 사실인데, 나는 dfs 라고 하면 그저 깊이 우선 탐색이라고만 생각했는데, 단순히 "모든 경우의 수를 재귀적으로 탐색" 하는 함수여도 dfs 라고 이름을 붙이는 경우가 많다고 한다. 내가 너무 깊이 우선 탐색이라는 거에만 꽂혀있었다는 사실을 새롭게 배우게 됐다.