[BOJ/백준] 2133 타일 채우기

● [문제번호 2133] 타일 채우기

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

2133번: 타일 채우기

 

● 알아야 할 것

: 다이나믹 프로그래밍

 

 

● 풀이 과정

: 여러 가지 경우의 수가 떠올라서 이렇게 하는게 맞나 싶어 구글링을 했더니

경우의 수를 많이 따지는 것이 맞았다.

 

: DP 풀이과정 (Bottom - Up)

1. 테이블 정의하기

→ dp[index] : index까지 타일로 채우는 경우의 수

 

2. 점화식 찾기

→ 3X홀수 벽을 타일로 채울 수 없으므로 N이 홀수일 때는 0 출력

2일 때, 4일 때, 6일 때, 8일 때를 그려보면서 규칙을 찾아나간다.

풀이과정 참고 링크에서 자세하게 알려주고 있어서

눈으로 글을 술술 읽으면 이해된다.

 

3. 초기값 정하기

→ 3X0 일 때 1가지고 생각하기

3X홀수는 0이고

3X2 는 3가지

 

 

● 주의 할 것

: 3X0 벽인 경우에 타일로 채우는 경우의 수는 1이다.

 

 

● 참고 할 것

: 풀이과정 참고

https://yabmoons.tistory.com/536

 

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// dp[index] : 3 X (index)벽을 타일로 채우는 경우의 수
int dp[31];
int N;

void program()
{
    // 초기값
    dp[0] = 1;
    dp[1] = 0;
    dp[2] = 3;
    
    // 점화식
    for(int i = 4; i <= N; i = i + 2)
    {
        dp[i] = dp[i - 2] * dp[2];
        
        for(int j = i - 4; 0 <= j; j = j - 2)
            dp[i] += (dp[j] * 2);
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N;
    
    // 3X홀수 크기는 채울 수 없다
    if(N % 2 == 1)
        cout << 0;
    else
    {
        program();
        
        cout << dp[N];
    }
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 1/2] - [401 - 다이나믹 프로그래밍 1 (연습)] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	15988	1, 2, 3 더하기 3	https://pirateturtle.tistory.com/214
2	1149	RGB거리	https://pirateturtle.tistory.com/215
3	1309	동물원	https://pirateturtle.tistory.com/216
4	11057	오르막 수	https://pirateturtle.tistory.com/217
5	9465	스티커	https://pirateturtle.tistory.com/218
6	2156	포도주 시식	https://pirateturtle.tistory.com/219
7	1932	정수 삼각형	https://pirateturtle.tistory.com/220
8	11055	가장 큰 증가 부분 수열	https://pirateturtle.tistory.com/221
9	11722	가장 긴 감소하는 부분 수열	https://pirateturtle.tistory.com/222
10	11054	가장 긴 바이토닉 부분 수열	https://pirateturtle.tistory.com/223
11	13398	연속합 2	https://pirateturtle.tistory.com/224
12	2133	타일 채우기	https://pirateturtle.tistory.com/225