[ C++ ] 2718 - 타일 채우기

 

문제의 대분류를 보면 비트마스킹과 DP로 되어있다. 하지만 아무리 생각을 해도 DP로는 어떻게 풀어야할지 몰라서 재귀를 이용해서 문제를 푸는 방법으로 접근하였다.

 

4 x 2인 경우 아래와 같이 5가지로 나올 수 있다.

 

위의 5가지 경우를 보면 현재 상태에 따라서 다음 상태가 어떻게 나올 수 있는지 알 수 있다.

이를 토대로 나올 수 있는 경우의 수를 계산하면 아래와 같다.

이를 토대로 코드를 작성하고 메모이제이션을 이용하면 시간을 줄일 수 있다.