[백준 1904] 알고리즘 25일차 : 01타일

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

1904번: 01타일

다이나믹 프로그래밍 C++

접근방법

이것도 그냥 피보나치다.

근데 입력이 1,000,000까지고 출력은 모든 이진수 개수%15746이다.

그래서 그냥 피보나치 처럼 풀어서 나눈 나머지를 출력하면 절대 값이 안나온다.

다행히 나머지를 구하는 것이라는 거

나머지를 구해야 하는거면 굳이 결과 값을 다 더하면서 갈 필요가 없다.

결과 값에서 15746로 나누어 떨어지는 만큼은 필요 없기 때문에

1부터 N까지 결과값을 저장할때 15746으로 나눈 나머지만 저장하면 된다.

 

소스코드

#include <iostream>
using namespace std;

int main(){
    int N;
    cin >> N;
    
    int cases[1000001];
    cases[1] = 1;
    cases[2] = 2;
    for(int i = 3 ; i <= N ; i++){
        cases[i] = (cases[i-1] + cases[i-2])%15746;
    }
    cout << cases[N];
    
    return 0;
}