백준 1904 01타일

문제

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

풀이전략

1. 결국 00타일과 1만을 사용할 수 있다.
2. 이러한 유형의 문제는 반드시 규칙을 가지기에 가지고있는 규칙을 찾아야한다.
3. N=4 일때를 예로들면 숫자가 1로시작할때, 00으로 시작할때 두가지 경우로 나누어서 풀면된다.

코드

#include<bits/stdc++.h>

using namespace std;


int N;
int dp[1000001];
const int MOD = 15746;
int main(){
    ios_base::sync_with_stdio(false);
    // freopen("../input.txt","rt",stdin);
    
    cin >> N;

    dp[1] = 1;
    dp[2] = 2;
    //dp[i-1] 은 숫자가 1로 시작할때, dp[i-2]는 숫자가 00으로 시작할 때의 경우의 수이다.
    for(int i=3; i<=N; i++){
        dp[i] = (dp[i-1] + dp[i-2])%MOD;
    }
    cout << dp[N] << endl;
    return 0;
}

소감

규칙을 찾고 풀면 되는 문제이고, O(N)으로 편하게 풀었다. 모든문제가 이 문제처럼 딱 보였으면 좋겠다... 제출할때 MOD로 나머지를 구해야하는것 잊지말자.