1. 17160 양팔저울(실버 I) 문제

무게가 서로 다른 k개의 추와 빈 그릇이 주어지면, 양팔저울을 한 번만 이용하여 원하는 무게의 물을 그릇에 담고자 한다. 주어진 k개의 모든 추의 무게 합을 S라고 할 때 1부터 S사이의 정수 중 양팔저울을 한번만 사용하여 측정이 불가능한 경우의수를 출력한다.

• 추의 개수는 3개 이상 13개 이하이다.

1-1) 접근법

무게가 서로 다른 k개의 추를 양팔저울에 올려놓는 경우의 수를 생각해보자. 빈그릇을 올려놓지 않는다고 가정하고, 양팔을 각각 왼쪽 | 오른쪽 이라고 가정하면

• 추를 왼쪽에 올린다.
• 추를 오른쪽에 올린다.
• 추를 올리지 않는다.

3가지 경우가 가능하다.

각각의 추에 대해 3가지 경우를 모두 확인해야한다. 특정 무게가 가능한지 확인하는 것이 아니고, 1부터 전체 무게의 합 중 불가능한 수치만 확인해야 하므로 해당 범위 중 가능한 값을 모두 확인해야 한다.

문제에 주어지는 추의 최대 개수는 13개이므로 최대 $3^{13}$(1,594,323)가지의 경우의 수를 살펴봐야 한다. 결국 O($3^n$)의 시간복잡도를 가지지만 최대 13개 이므로 전부 확인하더라도 문제의 조건인 1초 이내의 시간제한에도 문제 해결이 가능하다.

1-2) 문제 풀이

추를 왼쪽에 올리거나, 오른쪽에 올리거나, 올리지 않는다. 이 3가지를 재귀적으로 순회하면서 확인할 수 있을 것이다.

const dfs = (L, weights, weight, n) => {
  if (L === n) {
    if (weight > 0) {
      answer[weight] = true;
    }
  } else {
    dfs(L + 1, weights, weight + weights[L], n);
    dfs(L + 1, weights, weight - weights[L], n);
    dfs(L + 1, weights, weight, n);
  }
};

• L: Level, 여기서는 양팔저울에 올린 추의 개수를 나타낸다.
• weights: 주어진 추의 무게 배열
• weight: 양팔저울에 올린 추에 의해 계산된 확인 가능한 무게
• n: 전체 추의 개수
• answer: S + 1의 길이를 갖는 false로 초기화된 배열

추를 양팔저울에 올릴 때 양팔저울 한쪽을 기준으로 추를 올린다고 가정한다. 만약 왼쪽을 기준으로 한다면 왼쪽에 추를 올리는 것은 추의 무게를 더하고, 오른쪽에 올리는 것은 추의 무게를 뺀다. 추를 올리지 않는다면 무게를 그대로 둔다.

모든 추를 확인했을 때 가능한 무게라면 answer의 index로 접근해 answer 값을 true로 변경한다.

1-3) 전체 코드

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().split("\n");

const k = parseInt(input[0], 10);
const weights = input[1].split(" ").map((weight) => parseInt(weight, 10));

const S = weights.reduce((acc, cur) => acc + cur);
const answer = Array.from({ length: S + 1 }, () => false);
answer[0] = true;

const dfs = (L, weights, weight, n) => {
  if (L === n) {
    if (weight > 0) {
      answer[weight] = true;
    }
  } else {
    dfs(L + 1, weights, weight + weights[L], n);
    dfs(L + 1, weights, weight - weights[L], n);
    dfs(L + 1, weights, weight, n);
  }
};

dfs(0, weights, 0, k);

console.log(answer.filter((ans) => !ans).length);

2. 2629번 양팔저울(골드 III) 문제

양팔 저울과 몇 개의 추가 주어졌을 때, 이를 이용하여 입력으로 주어진 구슬의 무게를 확인할 수 있는지 결정하려고 한다.

구슬의 무게를 확인할 수 있으면 "Y", 구슬의 무게를 확인할 수 없으면 "N"을 출력한다.

• 추의 개수는 자연수이고, 30개 이하이다.
• 추의 무게들은 자연수로 가벼운 것부터 차례로 주어진다.(오름차순)
• 구슬의 개수는 7개 이하이다.
• 확인하고자 하는 구슬의 무게는 40,000보다 작거나 자연수이다.

• 위 그림의 경우 구슬의 무게는 3이다.

1-1) 접근법

우선 17160번 양팔저울과 비슷하지만 주어지는 추의 개수가 30개까지 늘어났고, 확인해야 하는 명확한 무게(구슬의 무게)가 input으로 주어진다.

17160번 양팔저울은 모든 가능한 무게를 확인한 다음 불가능한 무게를 반환하는 것이었다면, 2629번 양팔저울은 구슬의 무게를 확인 가능한지 불가능한지만 확인하면 된다.

전체적인 로직은 17160번 양팔저울과 유사하다. 이번에도 추를 양팔저울의 왼쪽에 올릴지, 오른쪽에 올릴지, 올리지 않을지를 결정해서 모든 경우의 수를 확인해본 후 구슬의 무게를 확인할 수 있는지 판단하면 된다.

다만, 여기서는 추의 개수가 최대 30개이므로 최대 $3^{30}$가지의 경우의 수를 살펴봐야 된다. 직접 계산해보지 않아도 모든 경우를 확인하는 것은 비효율적이다. 그래서, 이를 그대로 이용하되 조건을 추가해서 이미 무게를 확인했으면 더 이상 다음 경우의 수로 뻗어나가지 않도록 하는 최적화를 통해 문제를 해결해보자.

1-2) 문제 풀이

const dfs = (L, weights, weight, n) => {
  if (L === n + 1 || dp[L][weight] === true) {
    return;
  }

  dp[L][weight] = true;
  canWeigh[weight] = true;

  dfs(L + 1, weights, weight + weights[L], n);
  dfs(L + 1, weights, Math.abs(weight - weights[L]), n);
  dfs(L + 1, weights, weight, n);
};

• L: 양팔저울에 올려놓은 추의 개수
• weights: 주어진 추의 무게 배열
• weight: 양팔저울에 올린 추에 의해 계산된 확인 가능한 무게
• n: 전체 추의 개수
• dp: [추의 개수][구슬의 무게]로 이루어진 false로 초기화된 2차 배열
• canWeigh: 추의 최대 무게(40,000) 길이를 갖는 false으로 초기화된 배열

재귀적으로 호출하는 dfs 함수는 17160번 양팔저울과 크게 다르지 않다.

여기서는 추를 모두 올려놓기 전에 dp 배열을 이용해 캐시하여 만약 weight를 측정한 적이 있으면 더이상 진행되지 않게 return하는 부분이 추가되었다.

여기서 dp는 [30][40000] 길이를 갖는 2차배열이다. dp[L][weight]가 의미하는 것은 L개의 추를 사용해 weight 무게를 측정한 적 있는지 여부를 말한다. 추는 최대 30개, 구슬의 무게는 최대 40,000 이므로 dp의 길이를 30, 40000으로 설정한 것이다.

1-3) 전체 코드

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().split("\n");

const k = parseInt(input[0], 10);
const weights = input[1].split(" ").map((weight) => parseInt(weight, 10));
const s = parseInt(input[2], 10);
const goals = input[3].split(" ");

const dp = Array.from({ length: 31 }, () =>
  Array.from({ length: 40001 }, () => false)
);
const canWeigh = Array.from({ length: 40001 }, () => false);

const dfs = (L, weights, weight, n) => {
  if (L === n + 1 || dp[L][weight] === true) {
    return;
  }

  dp[L][weight] = true;
  canWeigh[weight] = true;

  dfs(L + 1, weights, weight + weights[L], n);
  dfs(L + 1, weights, Math.abs(weight - weights[L]), n);
  dfs(L + 1, weights, weight, n);
};

dfs(0, weights, 0, k);

for (let i = 0; i < s; i++) {
  if (goals[i] > 40000 || canWeigh[goals[i]] === 0) {
    console.log("N");
  } else {
    console.log("Y");
  }
}