DP 정리> 타일 채우기

# 문제 모음

11726번 - 2*n 타일링 

11727번 - 2*n 타일링 2

1793번 - 타일링 (2*n 타일링. 큰 숫자 다루기)

2133번 - 타일 채우기 (3*n 타일) 

2718번 - 타일 채우기 (4*n 타일)

-----------------------------------------

1720번 - 타일 코드 (타일 뒤집기)  :  기본 2*n 타일 문제에서, 중복되는 경우를 제거하기 위해 교집합을 더한 다음 /2 연산을 해준다

-----------------------------------------

1904번 - 01타일 (숫자 다루기) : 그냥 나열하다 보면 알아서 규칙이 나온다

# 기본적인 접근 방식 

- Top Down 접근 : 전체 완성본에서, width-1, width-2... 등등을 고려해서 식을 세운다

- Bottom Up 접근 : 1, 2, 3... 순서로 작은 것부터 큰 컷을 채워나간다

ex) 1904번 - 01타일

# 문제풀이 순서

1) 몇 차원의 배열이 필요할까? : 문제에서 필요로 하는 요소들을 정리해본다

* 1차원 : 

ex)  11726번 - 2*n 타일링

11727번 - 2*n 타일링 2,

2133번 - 타일 채우기 (3*n 타일) >> hard

* 2차원 : i 부터 j 까지의 경우에 대한 접근

* 3차원 : i 부터 j 까지에서, k 값을 가지는 경우에 대한 접근

ex) 

2) dp 배열을 정의한다

ex) dp[ i ][ j ][ k ] : i 부터 j 까지의 배열에서 k 의 색깔을 가질 최소한의 경우의 수

3) for 문 또는 재귀함수를 이용해서 정의한다

     * for 문 : 대부분의 문제들

     * 재귀함수 : 2718번 - 4*n 타일 채우기