(1904) 01타일

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

단계별로 풀어보기

21단계(동적 계획법 1) 3번째

 

 

 

dp[n]을 길이가 n인 만들 수 있는 수열의 개수라고 하자. 이때 n번째 수는 당연히 0 또는 1이다.

1) n번째 수가 1: 나머지 n-1개를 아무렇게나 채워도 된다. 이는 길이가 n-1인 수열의 개수와 같으므로 dp[n-1]

2) n번째 수가 0: 00타일만 쓸 수 있으므로 n-1번째 수도 0이다. 길이가 n-2인 수열의 개수와 같으므로 dp[n-2]

따라서 dp[n]= dp[n-1]+dp[n-2]이다.

또한 dp[1]= 1, dp[2]= 2이다. 문제에서 알려주긴 하지만 보통 점화식 범위를 벗어나는 기저값은 따로 구해줄 필요가 있다.

 

 

 

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

int main() 
{
  int n;
  
  cin >> n;
  
  vector<int> dp(n+1);
  
  dp[1]= 1;  dp[2]= 2;
  
  for(int i=3;i<=n;i++)  dp[i]= (dp[i-2]+dp[i-1])%p;
  
  cout << dp[n];
  
  return 0;
}