[백준] 알고리즘 14852. 타일채우기 3

[백준] 알고리즘 14852. 타일채우기 3

문제

2×N 크기의 벽을 2×1, 1×2, 1×1 크기의 타일로 채우는 경우의 수를 구해보자.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000,000)이 주어진다.

출력

첫째 줄에 경우의 수를 1,000,000,007로 나눈 나머지를 출력한다.

예제 입력 1

1

예제 출력 1

2

예제 입력 2

2

예제 출력 2

7

예제 입력 3

3

예제 출력 3

22

 

---

다이나믹 프로그래밍의 2차원 배열 적용 문제.

타일 채우기 1 문항과 같은 알고리즘을 적용한다면 제한 시간 초과하여 비효율적인 문제가 발생.

타일의 N칸이 3칸 추가되는 경우부터는 두 경우의 나눌 수 없는 고유의 모양 배치가 계속해서 나타나므로 2차원적 다이나믹 프로그래밍 적용이 가능. 

초기 값 arr[0][0], arr[1][0], arr[2][0], arr[2][1]을 설정해두고 3칸이 추가되는 arr[i][0], arr[i][1]부터 개념을 적용함.

점화식은 d[n] = 2 * d[n - 1] + 3 * d[n - 2] + 2 * d[n - x] ※ x >= 3, (n - x) >= 0 이므로

2차원 배열로 구현하면 2 * arr[i -1] + 3 * arr[i - 2] + 2 * arr[i][1] 이다.

 

예를 들어,

arr[3][0]은 14 + 6 + 2 = 22

arr[4][0]은 44 + 21 + 6 = 71