백준2635 - 수 이어가기 (완전탐색) node.js

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

문제는 해당 규칙에 따라 만들 수 있는 수열의 최대 길이와, 최대 길이를 이루는 수들을 출력하는 문제다.

 

문제 해결 방식

수의 범위가 3만 이하로 작은 편이고, 만들어지는 수열 역시 길이가 크게 길지 않을 것이라 판단하여 모든 경우의 수를 탐색하는 완전 탐색으로 접근했다.

N이 주어질 경우, 1부터 N까지 모든 경우를 대입하여 문제 요구에 따라 가장 길이가 길게 만들어지는 로직을 구현하면 된다.

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

function solution(data) {
  const N = +data[0];

  let result = [];
  for (let i = N; i > 0; i--) {
    const storage = [N, i];

    while (true) {
      const a = storage.at(-2),
        b = storage.at(-1);

      if (0 > a - b) {
        if (storage.length > result.length) result = storage;
        break;
      } else storage.push(a - b);
    }
  }

  console.log(result.length);
  console.log(...result);
}

solution(input);