백준 1904번 C++

백준 1904번 01타일

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

1904번: 01타일

정답 코드

#include<iostream>
using namespace std;
unsigned long long dp[1000001] = { 0,1,2,3 };
int main() {
	int n;
	cin >> n;
	if (n == 1 || n == 2)
		cout << n;
	else {
		for (int x = 3; x <= n; x++)
			dp[x] = (dp[x - 2] + dp[x - 1])%15746;
		cout << dp[n];
	}
}

문제 풀이

dp를 활용해서 푸는 문제입니다. 코드 구현 방식은 피보나치 수열을 구현하는 방식과 비슷합니다. 그리고 각 배열 원소 결과값을 15746으로 나눈 나머지로 저장자는 것이 중요합니다.