[백준] 2193번 - 이친수 (nodejs)

문제

2193번: 이친수

 

풀이

1. 이친수는 0으로 시작하지 않는다.
2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.

두 규칙에 의해 이친수는 반드시 10으로 시작한다.

 

자릿수에 따라 모든 가능한 경우를 나열해보면

 

N=1일 때 - 1개
1

 

N=2일 때 - 1개
10

 

N=3일 때 - 2개
100
101

 

N=4일 때 - 3개
1000
1001
1010

 

N=5일 때 - 5개
'1000'0
"100"01
'1001'0
'1010'0
"101"01

 

N=6일 때 - 8개
'10000'0
"1000"01
'10001'0
'10010'0
"1001"01
'10100'0
"1010"01
'10101'0

 

개수를 보면

1 + 1 = 2,

2 + 3 = 5

이런 식으로 i-1과 i-2의 개수를 더한 게 i 자리 이친수의 개수가 되는 것을 알 수 있다.

 

점화식
dp[i] = dp[i-1] + dp[i-2]

 

이렇게 귀납적으로 놓고 보니 점화식이 도출되었다.
하지만 귀납적인 방법 말고도 원리를 설명할 수 있다.

 

어떤 수 뒤에 0이 오는 건 자유롭다.
그렇게 끝자리가 0으로 끝나는 수는 이전 수와 0이 손을 잡은 것이므로 개수는 dp[i-1] 그대로이다.

 

어떤 수 뒤에 1이 오기 위해서는 안전하게 01을 덧붙이는 것이 좋다.
자릿수가 1개 더 늘어나는 문제는 i-2의 수 뒤에 01을 덧붙이는 것으로 해결할 수 있다.
그러면 1 다음에 1이 오지 않을 수 있으면서 101 + 01, 100 + 01 처럼 확실하게 끝자리가 1로 끝나게 할 수 있다.
그래서 개수는 dp[i-2]가 된다.

 

점화식은 dp[i] = dp[i-1] + dp[i-2]

 

💻 코드

const fs = require('fs');
const N = Number(fs.readFileSync('./input.txt').toString());

function solution() {
  const dp = Array(N + 1).fill(0);
  dp[1] = BigInt(1);
  dp[2] = BigInt(1);
  for (let i = 3; i <= N; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }

  return dp[N].toString();
}

console.log(solution());