이 문제는 이곳에서 확인할 수 있습니다.
이 문제는 00 타일과 1 타일을 가지고 만들 수 있는 2진수의 가짓수를 구하는 문제입니다.
N = 1 => 1
N = 2 => 00, 11
N = 3 => 001, 100, 111
N = 4 => 0000, 0011, 1100, 1001, 1111
N = 5 => 00001, 00100, 10000, 00111, 10011, 11001, 11100, 11111
dp[i] = dp[i-1] + dp[i-2] 임을 알 수 있다.
즉, i-1에서 각 타일의 뒤에 1 타일을 붙이고 i-2에서 각 타일의 뒤에 00 타일을 붙이는 것으로 이해할 수 있다. 앞뒤를 고려하지 않고 뒤에 붙이는 것만으로 모든 경우의 수를 구할 수 있다.
자바스크립트로 개발하는 새내기입니다.