이친수

문제

언어

  • JavaScript

문제 풀이 step 1

  • dp[n] = n자리 이친수의 개수
  • 이친수는 이진수 중에 0으로 시작하지 않으며, 1이 두번 역속 나오지 않는 수를 의미합니다.
  • DP의 특징인 작은 문제의 해답으로부터 큰 문제의 해답을 찾을 수 있다를 이용합니다.
  • 모든 이친수는 또한 이진수이기 때문에 0과 1로만 이루어져 있습니다.
  • 모든 경우는 2가지일 수 밖에 없습니다. ‘OOO…1’ 또는 ‘OOO…0’ 이런 형태입니다.
    • 뒤에 0이 오는 경우 dp[n][0] = dp[n-1][1] + dp[n-1][0]
    • 뒤에 1이 오는 경우 dp[n][1] = dp[n-1][0] (1은 두번 연속 불가능)

문제 풀이 step 2

  • 이 문제는 그냥 Number의 범위로 풀면 풀리지가 않습니다.
  • 확인해보니 Number 원시 값이 안정적으로 나타낼 수 있는 최대치인 2^53 - 1보다 큰 정수가 나오기 때문입니다.
  • 따라서 BigInt를 사용합니다.
  • BigInt는 정수 리터럴의 뒤에 n을 붙이거나, 함수 BigInt()를 호출해 생성할 수 있습니다.
    • typeof 10n === bigint
    • typeof BigInt(10) === bigint
  • MDN BigInt 문서

소스 코드

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

const solution = (input) => {
	const N = parseInt(input[0]);
	const dp = Array.from({length: N + 1}, () => []);

	// BASE
	dp[1][0] = BigInt("0");
	dp[1][1] = BigInt("1");

	for (let i = 2; i < N + 1; i++) {
		dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
		dp[i][1] = dp[i - 1][0];
	}

	return String(dp[N][0] + dp[N][1]);
};

console.log(solution(input));