타일 채우기 <다시풀기>

문제

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

입력

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

출력

첫째 줄에 경우의 수를 출력한다.

예제 입력 1

1
2

예제 출력 1

1
3

힌트

아래 그림은 3×12 벽을 타일로 채운 예시이다.

풀이

길이가 2인 타일은 총 3개있다.

이게 끝이 아니라

길이가 4인 타일도 2개 있다.

또

길이가 6인 타일도 2개있다..

즉,

점화식은

dp[n]=dp[n-2]x3 + dp[n-4]x2+ dp[n-6]x2 …..dp[0]x2 라는것 !!

어렵다,, ㅜㅜㅜㅜㅜ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>

using namespace std;

int main(){
    int dp[31]={0};
    int n; cin >> n;
    dp[0]=1;dp[1]=0;dp[2]=3;
    for(int i=3;i<=n;i++){
        dp[i]+=3*dp[i-2];
        for(int j=i-4;j>=0;j-=2){
            dp[i]+=2*dp[j];
        }
    }
    cout <<dp[n];
}

• Previous
  [BOJ]1699 제곱수의 합 <다시풀기>
• Next
  [BOJ]2580 스도쿠 <다시풀기>