백준 1904번: 01타일

[문제 링크]

1904번: 01타일

---

https://onlytrying.tistory.com/81 타일 문제와 비슷한 유형의 문제라고 생각한다.

 

N == 1일 때 만들 수 있는 타일은 1 한가지 존재하고,

N == 2일 때 만들 수 있는 타일은 00, 11 두가지 존재한다.

N == 3일 때 만들 수 있는 타일은 N==1일 때 만들 수 있는 타일 뒤에 N==2일 때 만들 수 있는 타일을 붙인 모양(100, 111)과 새롭게 만들 수 있는 001이 추가되어 세가지 존재하게 된다.

 

이를 통해 앞서 많이 풀어봤던 타일채우기 문제들과 동일한 유형의 문제임을 알 수 있다.

따라서 점화식은 다음과 같다.

 

dp(N) = dp(N-2) * 2 + dp(N-3)

---

#include <iostream>
using namespace std;

const int MOD = 15746;
int memo[1000001];

int Topdown(int N)
{
	if (N == 1) return 1;
	if (N == 2) return 2;
	if (N == 3) return 3;

	int& ret = memo[N];
	if (ret != 0) return ret;

	return ret = (Topdown(N - 2) * 2 + Topdown(N - 3)) % MOD;
}

int Bottomup(int N)
{
	memo[1] = 1;
	memo[2] = 2;
	memo[3] = 3;

	for (int i = 4; i <= N; i++)
		memo[i] = (memo[i - 2] * 2 + memo[i - 3]) % MOD;

	return memo[N];
}

int main(void)
{
	int N;
	cin >> N;

	cout << Topdown(N) << endl;

	cout << Bottomup(N) << endl;
	
	return 0;
}

알고리즘 200일 프로젝트 - 87 day