[BOJ 2653] 수 이어가기

문제

수 이어가기

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

 

 

풀이

설명

규칙에 맞춰 만들어지는 최대 개수의 수들을 구하는 문제입니다.

 

규칙은 다음과 같습니다.

1. 첫 번째 수로 양의 정수가 주어집니다.
2. 두 번째 수는 양의 정수 중에서 하나를 선택합니다.
3. 세 번째부터 이후에 나오는 모든 수는 앞의 앞의 수에서 앞의 수를 빼서 만듭니다. 예를 들어, 세 번째 수는 첫 번째 수에서 두 번째 수를 뺀 것이고, 네 번째 수는 두 번째 수에서 세 번째 수를 뺀 것입니다.
4. 음의 정수가 만들어지면, 이 음의 정수를 버리고 더 이상 수를 만들지 않습니다.

 

주어진 수를 N이라 할 때,

N의 절반에 해당하는 수부터 N까지 1씩 증가시키며 규칙에 맞춰 수열을 만들어 구합니다.

 

예시 코드

function solution() {
  const N = Number(input());
  let longestNums = [];
  const startNum = Math.floor(N / 2) + 1;

  for (let i = startNum; i <= N; i++) {
    const nums = [N, i];
    while (true) {
      const len = nums.length;
      const nextNum = nums[len - 2] - nums[len - 1];
      if (nextNum < 0) break;
      nums.push(nextNum);
    }
    if (nums.length > longestNums.length) longestNums = nums;
  }

  return longestNums.length + "\n" + longestNums.join(" ");
}