백준 c++ 1904 "01타일" -PlusUltraCode-

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

 

 

 

 

 

 

 

[필자 사고]

 

문제를 보고 일단 N=4까지 구해보았다.

 

N=1 일때     타일 종류 1          총 1개

 

2일때            타일 종류 00 11  총 2개

 

3일때      타일 종류 001, 100, 111 총 3개

 

4일때  타일종류 0000 ,0011 1100 1111 1001 총 5개

 

5일때는 00001, 00100, 00111 10000, 10011, 11001, 11100, 11111 총 8개이다.

 

규칙성을 찾아보면 피보나치 수열이라는 점을 알 수 있다. 

 

동적프로그래밍 문제를 풀 때는 어느정도의 특수한 상황을 항상 생각하면서 풀어야 될 거같다.

 

[소스 코드]

#include <iostream>
#include <vector>


using namespace std;


int N;

vector<long> Dp;

void Input() {
	cin >> N;
	Dp.resize(1000001);
	Dp[1] = 1;
	Dp[2] = 2;
	
}

void Solve() {
	for (int i = 3; i <= 1000000; i++) {
		Dp[i] = Dp[i - 2] + Dp[i - 1];
		Dp[i] %= 15746;
	}
	
}

int main(void) {
	Input();
	Solve();
	cout << Dp[N];
}