[백준 13301번] 타일 장식물 (C++)

문제링크 : https://www.acmicpc.net/problem/13301

13301번: 타일 장식물

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

ll dp[81];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    int N;
    cin >> N;
    
    dp[1] = 4;
    dp[2] = 6;

    for(int i=3; i<=N; i++)
    {
        dp[i] = dp[i-1] + dp[i-2]; //점화식
    }

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

크게 설명할 것 없는 DP 문제이다.

 

몇가지 경우의 수를 나열해보면,

dp[1] = 4;

dp[2] = 6;

dp[3] = 10;

dp[4] = 16

인 것을 볼 수 있는데 이를 통해서 dp[i] = dp[i-1] + dp[i-2]인 것을 구할 수 있다.

 

그리고 중요한 것이 수의 범위가 크기 때문에 long long으로 선언해줘야 한다.

실제 백준 채점 현황을 보면 long long을 안하고 int로 선언해서 74점을 맞은 현황을 간간히 볼 수 있다.