[Javascript/자바스크립트] 백준 27134번 Subset Sums

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

코드

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

function solution(n) {
  let total = (n * (n + 1)) / 2;
  if (total % 2 === 1) return 0;

  let dp = Array.from(new Array(n + 1), () => new Array(total / 2 + 1).fill(0));
  for (let i = 0; i < n + 1; i++) {
    dp[i][0] = 1;
  }

  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= total / 2; j++) {
      dp[i][j] = dp[i - 1][j];
      if (j - i >= 0) {
        dp[i][j] += dp[i - 1][j - i];
      }
    }
  }
  return dp[n][total / 2] / 2;
}

console.log(solution(n));

 

코드 설명

1. 1부터 N까지 모든 정수의 합 total을 구한다. 만약 이 total이 홀수라면 같은 합을 가진 두 개의 집합으로 나눌 수 없기 때문에 0을 리턴한다.

2. 행의 길이가 N+1, 열의 길이가 total+1인 2차원 배열 dp를 만든다. dp[i][j]에는 1부터 숫자 i까지의 수 중에 골라서 합이 j인 집합을 만들 수 있는 경우의 수가 저장된다. dp[i][0]은 합 0인 집합을 만들 수 있는 경우의 수를 말하므로 이 경우에는 모두 1이 된다.

3. 2중 for문으로 dp의 값을 하나씩 구한다.

$$dp[i][j]=\left\{\begin{matrix}
dp[i-1][j] \; (\textrm{if} \; j-i <  0)\\
dp[i-1][j]+dp[i-1][j-i] \; (\textrm{if} \; j-i \geq 0) \\
\end{matrix}\right.$$

4. 모두 돌고 난 뒤에 dp[n][total/2]에 저장된 값이 답이다.

 

느낀 점

처음에 DFS, BFS, 백트래킹 등 다양한 방법을 시도해봤지만 모두 시간 초과로 실패했다. 그래서 아예 관점을 바꿔서 생각해보니 이건 0-1 knapsack 문제라는 걸 알 수 있었다.

 

문제의 풀이 방법은 매우 쉽지만, 해결 방법을 찾지 못해서 많이 헤맸고, 자바스크립트가 아직 익숙하지 못해서 파이썬으로 먼저 풀고 자바스크립트로 옮기는 방법을 썼던 것이 아쉽다. 앞으로 자바스크립트로 알고리즘 문제를 계속 풀며 문제 해결 역량과 자바스크립트 이해도를 높여야겠다.

 

아래가 자바스크립트로 작성하기 이전에 작성했던 동일한 로직의 파이썬 코드이다.

파이썬 코드

n = int(input())


def solution(n):
    total = n*(n+1)//2
    if total % 2 == 1:
        return 0
    dp = [[0]*(total//2+1) for _ in range(n+1)]

    for i in range(n+1):
        dp[i][0] = 1

    for i in range(1, n+1):
        for j in range(1, total//2+1):
            dp[i][j] = dp[i-1][j]
            if j-i >= 0:
                dp[i][j] += dp[i-1][j-i]
    return dp[n][total//2]//2


print(solution(n))