덧셈사슬 구하기

addition-chain.js

// 트리 노드
function Node(value, parent = null) {
  this.value = value; // 덧셈사슬을 구할 수
  this.parent = parent; // 부모 노드
  this.count = 0; // 최소덧셈
}

function getAdditionChain(to = 99) {
  const minCounts = new Array(to + 1).fill(to);
  minCounts[0] = null; // 배열은 1부터 사용합니다.

  const queue = [];
  queue.push(new Node(1));
  while (queue.length > 0) {
    const term1 = queue.shift();
    let term2 = term1;

    if (term1.value > to) continue;

    if (minCounts[term1.value] < term1.count) continue;
    minCounts[term1.value] = term1.count;

    while (true) {
      const newNode = new Node(term1.value + term2.value, term1);
      newNode.count = term1.count + 1;
      queue.push(newNode);

      if (term2.parent === null) break;
      else term2 = term2.parent;
    }
  }
  return minCounts;
}

console.table(getAdditionChain(99));

브라우저 콘솔에 복붙하시면 됩니다.