백준 2133: 타일 채우기

• 

   2133번
• 제출
• 맞힌 사람
• 숏코딩
• 재채점 결과
• 채점 현황
• 내 제출
•  난이도 기여
• 강의
• 질문 검색

타일 채우기 성공다국어

한국어   

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

36028

12732

10028

35.296%

문제

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

입력

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

출력

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

예제 입력 1 복사

2

예제 출력 1 복사

3

힌트

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

코드

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin >> n;

    int dp[31] = { 0 };

    dp[0] = 1;
    dp[2] = 3;

    for (int i = 4; i <= n; i++)
    {
        dp[i] = dp[i - 2] * 3; 
        for (int j = 4; j <= i; j += 2)
        {
            dp[i] += dp[i - j] * 2; 
        }
    }

    cout << dp[n];
    return 0;
}