백준 1904번: 01타일

 

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

1904번: 01타일

 알고리즘 

 

N=1 일 때 2진 수열의 개수 : 1

N=2 일 때 2진 수열의 개수 : 2

N=3 일 때 2진 수열의 개수 : 3

N=4 일 때 2진 수열의 개수 : 5

                 .

                 .

                 .

전형적인 피보나치 수열임을 알수있고 출력을 15745으로 나눈 나머지를 출력하여야되는데 

마지막 출력 직전에 15745로 나누면 안되고 계산하는과정에서 미리 나머지를 저장해야된다 안그러면 에러발생 .

 

주의사항 : 여기서 N이 95정도만 넘으면 int 범위를 초과하기 때문에 long long 으로 지정해둠

 

 코드 

 

 

 

#include<iostream>
 
using namespace std;
 
typedef long long ll;
 
ll arr[1000001];
 
ll func(int n) {
    //종료부
    if (n == 1) return 1;
    if (n == 2)return 2;
 
    //메모리 제이션
    if (arr[n]) return arr[n];
    arr[n] = (func(n - 1) + func(n - 2))%15746;
 
    return arr[n];
 
}
 
int main() {
 
    int N;
    cin >> N;
    cout << func(N);
}