[백준/C++] 1904번: 01타일

문제

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

---

문제 요약

0 또는 1이 쓰여 있는 낱장의 타일이 있고, 타일들을 붙여 길이 n인 타일을 구성하려 한다.

 

이 때, 0이 쓰여 있는 타일은 하나를 사용할 수 없고 붙여서 00으로만 사용할 수 있다.

 

길이가 n인 타일 종류 개수를 출력한다.

---

코드

#include <iostream>

using namespace std;

int n;
int dp[1000010];

int main() {
    // 입출력 단축 코드
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;

    dp[1] = 1;
    dp[2] = 2;

    for (int i = 3; i <= n; i++) {
        dp[i] = (dp[i - 1] + dp[i - 2]) % 15746;
    }

    cout << dp[n];

    return 0;
}

---

코드 설명

다이나믹 프로그래밍을 통해 문제를 해결한다.

 

n이 1일 경우,=> 1

 

n이 2일 경우,=> 00, 11

 

n이 3일 경우,=> 100, 000, 111

 

n이 4일 경우,=> 0000, 1100, 1001, 0001, 1111

 

차례로 나열해보면 점화식을 세울 수 있다.

 

dp[i] = dp[i - 2] + dp[i - 1]