13301 타일장식물👊

문제

대구 달성공원에 놀러 온 지수는 최근에 새로 만든 타일 장식물을 보게 되었다. 타일 장식물은 정사각형 타일을 붙여 만든 형태였는데, 한 변이 1인 정사각형 타일부터 시작하여 마치 앵무조개의 나선 모양처럼 점점 큰 타일을 붙인 형태였다. 타일 장식물의 일부를 그리면 다음과 같다.


그림에서 타일에 적힌 수는 각 타일의 한 변의 길이를 나타낸다. 타일 장식물을 구성하는 정사각형 타일 한 변의 길이를 안쪽 타일부터 시작하여 차례로 적으면 다음과 같다.

1, 1, 2, 3, 5, 8, ...

지수는 문득 이러한 타일들로 구성되는 큰 직사각형의 둘레가 궁금해졌다. 예를 들어, 처음 다섯개의 타일이 구성하는 직사각형(위에서 빨간색으로 표시한 직사각형)의 둘레는 26이다.
타일의 개수 N(1 ≤ N ≤ 80)이 주어졌을 때, N개의 타일로 구성된 직사각형의 둘레를 구하는 프로그램을 작성하시오.

입력

표준 입력으로 다음 정보가 주어진다. 입력은 한 줄로 구성되며 이 줄에는 타일의 개수를 나타내는 정수 N(1 ≤ N ≤ 80)이 주어진다.

출력

표준 출력으로 N 개의 타일이 구성하는 타일 장식물 직사각형의 둘레를 출력한다.

64비트 정수형인 “long long” 자료형을 써야할 수 있음

예제 입력1

5

예제 출력1

26

예제 입력2

6

예제 출력2

42

코드

✔ 피보나치수열을 이용해서 둘레를 구해주면 된다. 둘레를 구할 때 표를 그려서 이해하면 쉽다.

// 타일 개수 1 2 3 4 5 6 7
// 둘레 4 6 10 16 26 42 68
따라서, f(n) = f(n-1) + f(n-2)의 규칙으로 증가함을 알 수 있다.
1과 2일때는 f(n-2)가 성립되지 않기때문에 배열에 [0,4,6]을 넣어준 뒤 구해지는 값들을 push해준다. 60~70번째까지 가면 숫자 초과 현상이 일어나는데 BigInt를 쓰면 뒤에 n이 붙어서 자꾸 틀렸다고 나온다... 일단 알고리즘은 맞는것 같으니 올리도록 하겠다...
(이거 아시는 분 헬프미ㅠ)

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const range = (start, end) => {
  let array = [];
  for (let i = start; i < end; ++i) {
    array.push(i);
  }
  return array;
};

let answer = [0, 4, 6];
const resultTile = (input) => {
  if (input === 1) return 4;
  if (input === 2) return 6;
  else {
    for (let i of range(3, 81)) {
      answer.push(answer[i - 1] + answer[i - 2]);
    }
    return answer[input];
  }
};

let input = 0;
rl.on("line", (userInput) => {
  input = userInput;
}).on("close", () => {
  console.log(resultTile(input));
  process.exit();
});