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

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

1904번: 01타일

 

 

 

 

---

- 문제

 

  00과 1 이 두개의 타일이 주어질 때 만들 수 있는 타일의 모양 개수를 구하는 문제다.

 

 

---

- 해설

 

N의 길이가 길어짐에 따라 

 

1일때 1

2일때 2

3일때 3

4일때 5

와 같이 

재귀함수의 형식을 띄고 있다는 것을 토대로 문제를 해결할 수 있다.

 

 

 

 

---

- 풀이

#include <iostream>
#include <vector>
using namespace std;

int main() // 15746의 나머지 구하는거 깜빡해서 한 5분 날림 ㅠㅠ
{

    int n;
    vector<int> f;
    f.reserve(1000001);
    cin >> n;

    f.push_back(1);
    f.push_back(2);
    for (int i = 2; i < n; i++)
    {
        f.push_back((f[i - 1] + f[i - 2]) % 15746);
    }
    cout << f[n - 1];

    return 0;
}

 

 

---

- 새롭게 알게 된 점