백준 알고리즘 2133 타일 채우기

안녕하세요.

전상수 입니다.

오늘 풀어볼 문제는 타일 채우기 입니다.

푸는 방식이 생각이 안나면 까다로운 문제인데 풀어보겠습니다.

위의 그림과 같이 n x 3 크기의 벽을 2 x 1, 1 x 2 타일로 채우는 경우의 수를 구하는 문제입니다.

벽에 타일을 놓았다고 할때 만들어질 수 있는 타일의 경우의 수는 9가지 입니다.

◻︎◻︎  ◼︎◻︎  ◼︎◼︎  ◻︎◻︎  ◼︎◼︎  ◼︎◻︎  ◻︎◻︎  ◼︎◻︎  ◻︎◻︎

◻︎◻︎  ◼︎◻︎  ◻︎◻︎  ◻︎◻︎  ◼︎◼︎  ◻︎◻︎  ◼︎◼︎  ◼︎◼︎  ◼︎◻︎

◻︎◻︎  ◻︎◻︎  ◻︎◻︎  ◼︎◻︎  ◻︎◻︎  ◻︎◻︎  ◼︎◻︎  ◻︎◻︎  ◼︎◻︎   

여기서 4,6,7,8 의 경우가 이상하다고 생각하실 겁니다.  어떤식으로 저런 타일이 나왔냐면

4의 경우 ◼︎◻︎ 타일인데 왼쪽 한줄 완성된걸 지워버렸습니다. 6번도 마찬가지고, 7,8 번의 경우 4,6번에서 

              ◼︎◻︎

              ◼︎◼︎

파생되는 타일입니다.

1번 타일에서 갈 수 있는 타일은 1,2번이고, 

2번에서 갈 수 있는 타일은 4번,

3번에서 갈 수 있는 타일은 5,6 번 입니다. 

그러면서 3칸이 완성된 부분은 제거해 나갔습니다. 

완성된 코드를 보면 남은 타일의 줄(len)과 타일 패턴(state)으로 dp배열을 만들어서 사용했습니다.

그리고 남은 타일이 없을때 갯수를 증가 시켜주는 식으로 코드를 구현하였습니다.

감사합니다.