[BOJ/2133] 타일 채우기

(공감과 댓글 하나는 글쓴이에게 큰 힘이 됩니다.)

 

문제 링크

- https://www.acmicpc.net/problem/2133

 

사용 알고리즘

- DP

 

풀이

- d[i] = 3 * i를 채우는 방법의 수

- d[i] = 3 * d[i - 2] + 2 * d[i - 4] + 2 * d[i - 6] + ...

→ 아래 그림의 경우도 고려해야 한다.

소스 코드

- https://github.com/moomini/algorithm/blob/master/boj/2133.cpp

#include <cstdio>   int d[33];   int main(void) {     int n; scanf("%d", &n);     d[0] = 1;     for (int i = 2; i <= n; i += 2) {         d[i] += (3 * d[i - 2]);         for (int j = i - 4; j >= 0; j -= 2) d[i] += (2 * d[j]);     }     printf("%d\n", d[n]);     return 0; } Colored by Color Scripter

cs