[BOJ][DP] 1904. 01타일

문제 -> https://www.acmicpc.net/problem/1904

N이 홀수일 때, N이 짝수일 때 

어떤 경우가 나올지 잘 생각해보면 

금방 답이 도출이 된다..

아래 그림을 보자. 

먼저 N=0일 때,

타일을 배치하지 않는다 라는 선택도 

경우의 하나에 속하므로 1. 

N = 1일 때, 

1밖에 놓을 수 없으므로 경우는 1. 

N = 2일 때, 

00, 11 두 개밖에 놓을 수 없으므로 2.

이제부터가 중요하다 .

N = 3일 때,

100, 001, 111로 총 세가지이다.

N이 홀 수라면,

낱개로서 배치할 수 있는 타일인 

"1"한개가 들어가는 경우가 생긴다.

그래서 경우의 수에 영향을 주게된다.

여기서 가만보면

어떤 점화식을 도출해낼 수가 있다.

dp[i] = dp[i - 2] * 2 + dp[i-3]

위와 같이 점화식이 성립이 된다. 

(왜 이런 점화식인지 아래 가서 설명한다)

N = 4, N = 5

N이 4, 5일때도 역시 마찬가지로 성립한다.

그렇다면 왜 이런 점화식이 나온 것일까?

아까 필자가 주목하라던 N = 3을 잘 생각해야 한다.

dp[i] = dp[i - 2] * 2 + dp[i-3]

위 식에서 

dp[i - 2]의 의미는,

뒤에 2칸이 채워져있는 상태를 의미하고

* 2의 의미는 아래와 같이 2칸이 채워질 수 있는 경우는 00, 11 밖에 없기에

어떤 한 경우에 대해 00, 11이 뒤에 붙게 되므로 각각 *2개씩 된다.

dp[i-3]의 의미도 마찬가지로 

뒤에 3자리가 채워져있다고 할 때, (001, 100, 111)

앞의 나머지 자리의 경우의 수를 고려 하는 것.

여기에 왜 곱하는 것이 없냐면

실제로 dp[i-3]의 경우들을 거꾸로 돌려보면 

뒤에 3자리가 붙어 있는 경우를 제외한 

나머지 경우들은 dp[i-2] * 2와 중복된다. 

 

소스(Github)