[백준/C++]1904번_01타일

문제는 다음과 같습니다.

만들어서 붙일 수 있는 타일은 00, 1 총 두 가지 종류입니다.
바로 n번째 상황에 대해서 생각을 해보면,

n번째 상황에 대해서, 타일은 마지막이
"00 으로 끝나거나" 또는 "1 로 끝나는 경우" 두 가지 입니다.

• 00 으로 끝나는 경우 만들 수 있는 타일의 수 : dp[n-2]
• 1 로 끝나는 경우 만들 수 있는 타일의 수 : dp[n-1]

따라서 길이가 N인 타일을 00과 1로 만들 수 있는 경우의 수는
dp[N] = dp[N-2] + dp[N-1] 입니다.

전체 코드는 다음과 같습니다🙆🏻‍♀️

#include <iostream>
#include <vector>
#define MOD 15746
using namespace std;

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  int dp[1000001]; int n; cin>>n;
  dp[1]=1; dp[2]=2;

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

  cout<<dp[n]<<"\n";
  return 0;
}