백준 1904번 01타일

백준 1904번

01 타일

---

동적 계획법으로 문제를 해결할 때, 규칙을 찾는 것 그리고 우리가 동일하게 반복적으로 하는 선택이 무엇이 있는지 생각하는 것이 좋다.

현재 사용할 수 있는 타일은 '1' 과 '00' 두 가지 타일이다.

이것이 우리가 동일하게 반복적으로 하는 선택이다.
1 과 00을 선택하여 타일을 만드는 것.

처음 1, 2 길이의 타일의 종류를 먼저 살펴본다.

길이가 1인 경우 : '1'
길이가 2인 경우 : '00', '11'

여기서 길이가 3인 경우를 살펴보면

길이가 3인 경우 : '100', '001', '111'

이걸 다시 생각해보면

• 길이가 i-2인 타일에 길이가 2인 00을 붙이는 경우

• 길이가 i-1인 타일에 길이가 1인 1을 붙이는 경우

의 두 가지 경우로 길이가 i에 도달한다는 것을 알 수 있다.

이것이 i>=3 에 대해서 반복되는 규칙이다.

길이 i인 타일의 개수를 dp[i] 라고 할 때, 점화식은

dp[i] = dp[i-2] + dp[i-1] 이다.

추가적으로 문제에서 15746으로 나눈 나머지를 요구하기 때문에
dp[i] = (dp[i-2]+dp[i-1]) % 15746 이 된다.

---

소스코드는 아래와 같다.