다이나믹 프로그래밍, 메모이제이션을 사용하여 풀어야 하는 문제이다.
2xN 직사각형을 1x2, 2x1, 2x2 타일로 채우는 경우의 수를 구를 2X(최대 1000)까지 구한다.
즉 반복되는 작업을 한다 -> 수열이 형성된다 라는 점을 기억해야한다.
1*2 -> A
2*1 -> B
2*2 -> C
라고 생각해보자
1) N이 1일 때
- B 한가지만 들어갈 수 있다.
- F(1) = 1
2) N이 2일 때
- AA, BB, C
- F(2) = 3
3) N이 3일 때
- AAB, BAA, CB, BC, BBB
- F(3) = 5
4) N이 4일 때
- AAAA, BBBB, AABB, BBAA, BAAB, AAA, CAA, BBC, CBB, BCB, CC
- F(4) = 11
이 떄, N이 4 이상일 경우, F(N) = F(N - 1) + (F(N - 2) * 2)
의 일반항을 도출할 수 있고 이를 메모이제이션하여 출력해주면 된다.
문제의 반복성과 규칙성을 찾아내 일반항을 도출하는 것
-> 다이나믹 프로그래밍으로 해결할 수 있다.
'백준 알고리즘 (Baekjoon Algorithm)' 카테고리의 다른 글
| [파이썬] 백준 알고리즘 No.6588 골드바흐의 추측 (0) | 2021.12.28 |
|---|---|
| [파이썬] 백준 알고리즘 No.2193 이친수 (1) | 2021.12.27 |
| [파이썬] 백준 알고리즘 No.4963 섬의 개수 (0) | 2021.12.24 |
| [파이썬] 백준 알고리즘 No.14562 태권왕 (0) | 2021.12.24 |
| [파이썬] 백준 알고리즘 No.16174 점프왕 쩰리 (Large) (0) | 2021.12.22 |