백준 js 1182번

<문제>

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

 

 

<문제 핵심>

 

1. 백 트래킹 알고리즘을 활용해서 부분수열의 합을 구한다음 합이 S와 일치하다면 dfs 재귀함수 로직이 종료되는 것이 핵심. 백 트래킹 알고리즘의 핵심은 재귀함수가 끝나는 시점을 구현해줘야 한다. 영상에서 알려준 팁으로는 트리 구조를 통해서 노트에 그려보면 이해하는데 도움이 된다고 한다. 

 

 

<Youtube에서 백트래킹 알고리즘 영상>

https://www.youtube.com/watch?v=atTzqxbt4DM&t=683s&pp=ygUZ67Cx7Yq4656Y7YK5IOyVjOqzoOumrOymmA%3D%3D

 

 

<문제 풀이과정 및 순서도 / 전체 코드>

1.  입력받은 다음 sol 함수 내부에 dfs 재귀탐색 로직을 구현한다.

✅ pick배열을 이용하여 부분 수열을 구성하고 dfs를 재귀적으로 호출하게 되는데 현재 인덱스의 숫자를 포함하거나 포함하지 않는 두 가지 경우를 재귀적으로 탐색한다.

✅ S가 0일 때 공집합도 부분수열로 카운트되므로, 이를 제외해야 한다.(처음에 이거 누락했음)

const input = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
  .toString()
  .trim()
  .split("\n");

const sol = (input) => {
  const [N, S] = input[0].split(" ").map(Number);
  input = input[1].split(" ").map(Number);
  let count = 0;

  const pick = [];
  function dfs(L) {
    if (L === N) {
      const sum = pick.reduce((sum, val) => sum + val, 0);
      if (sum === S) count++;
      return;
    }
    pick.push(input[L]);
    dfs(L + 1);
    pick.pop();
    dfs(L + 1);
  }
  dfs(0);

  if (S === 0) count--; // pick이 아무것도 선택하지 않았을 때 sum=0이므로 정답보다 1이 더 크므로, 감소시켜준다.
  return count;
};

console.log(sol(input));

 

 

<7월 12일 기준 ChatGPT를 이용해서 자세한 로직 질문>

첫 번째 가지 (첫 번째 원소 포함)

1. dfs(0):
   • 포함: pick = [-7]
   • 호출: dfs(1)
2. dfs(1):
   • 포함: pick = [-7, -3]
   • 호출: dfs(2)
3. dfs(2):
   • 포함: pick = [-7, -3, -2]
   • 호출: dfs(3)
4. dfs(3):
   • 포함: pick = [-7, -3, -2, 5]
   • 호출: dfs(4)
5. dfs(4):
   • 포함: pick = [-7, -3, -2, 5, 8]
   • 호출: dfs(5) (기저 조건 도달, sum = 1)
6. 백트래킹: pick = [-7, -3, -2, 5] ❗ 8을 포함하지 않은 경우를 의미 
   • 포함하지 않음: dfs(5) (기저 조건 도달, sum = -7)
7. 백트래킹: pick = [-7, -3, -2]
   • 포함하지 않음: dfs(4) (계속)