[BOJ] 1904 "01타일" 문제 풀이 & 소스 코드 With C/C++

#INFO

난이도 : SILVER3

알고리즘 유형 : DP

출처 : 1904번: 01타일 (acmicpc.net)

1904번: 01타일

---

#SOLVE

DP를 이용해 문제를 풀이하였습니다.

문제의 핵심은 타일의 마지막 수가 0으로 끝나는지 1로 끝나는지에 따라 케이스를 구분해 점화식을 세우는 것입니다.

마지막 수가 1로 끝나는 타일들은 DP[i-1] 값의 타일들에서 오른쪽에 1타일을 추가한 것이고, 마지막 수가 0으로 끝나는 타일들은 DP[i-2] 값의 타일들에서 오른쪽에 00타일을 추가한 것 입니다.

따라서 다음과 같이 점화식을 세우면 됩니다.

	//init
	dp[1] = 1;
	dp[2] = 2;
	
	//solve
	int n;
	cin >> n;
	for (int i = 3 ; i <= n ; i++) {
		dp[i] = (dp[i-2] + dp[i-1]) % 15746;
	}

---

#CODE

#include <iostream>
using namespace std;
int main(){
	//init
	long long dp[1000001];
	dp[1] = 1;
	dp[2] = 2;
	
	//solve
	int n;
	cin >> n;
	for (int i = 3 ; i <= n ; i++) {
		dp[i] = (dp[i-2] + dp[i-1]) % 15746;
	}
	
	cout << dp[n];
	return 0;
}