[1904] 01타일

---

처음에는 00타일과 1타일로 만들 수 있는 경우의 수를 백트래킹을 이용하여 풀어보았다.

#include <iostream>
#include <string>
using namespace std;

int N;

string m[1000001];
int cnt;

void dp(int count, string before, bool is_done) {
	if (count == N) {
		cnt++; 
		return;
	}
	
	if (before == "0" && is_done == false) { // 0이 하나만 쓰였을 때
		m[count] = "0";
		is_done = true;
		dp(count + 1, m[count], is_done);
	}

	else { // 0이 다 쓰여져있거나 그 전 값이 1이었던 경우
		if (count == N - 1) { // 맨 마지막 값에는 0이 들어가면 안됨. 0은 항상 2개씩 들어가야하므로
			m[count] = "1";
			is_done = true;
			dp(count + 1, m[count], is_done);
		}
		else {
			m[count] = "0";
			is_done = false;
			dp(count + 1, m[count], is_done);

			m[count] = "1";
			is_done = true;
			dp(count + 1, m[count], is_done);
		}
	}

}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;

	dp(0,"-1", false);

	cout << cnt % 15746;

}

답은 잘 나왔는데 시간 초과 떴다

 

 

그래서 푸는 방식을 아예 바꿔보았다.

전에 CodeUp에서 풀었던 [2601] 피보나치 수열을 참고하였다.

https://codeup.kr/problem.php?id=2601 

피보나치 수열

 

여기서는 배열을 생성하고 그 배열에 답을 계속 넣어주었다. 그렇게 count를 증가시켜 N번째 피보나치 수열일 때 return으로 끊어주었다.

#include <iostream>
#include <cmath>
using namespace std;

int n, memo[41];

void f(int x) {
	if (x == 1 || x == 2) {
		memo[x] = 1;
	}
	else {
		if (memo[x] == 0) memo[x] = memo[x - 1] + memo[x - 2];
	}
	if (x == n) return;
	f(x + 1);
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;

	f(1);

	cout << memo[n];
}

이 코드를 다시 활용해보기로 하였다.

 

대신 이 코드를 풀려면 경우의 수를 다 찾는게 아니라 길이가 N인 2진수열의 개수들의 규칙을 알아야한다.

길이가 N인 2진 수열의 개수 M[N] = M[N - 1] + M[N - 2] 인데 문제에서 15746로 나눈 나머지를 구하라고 했으므로 % 15746을 붙여줘야 한다.

N = 1, 2, 3일 때는 N과 개수가 동일하므로 따로 처리해주었다.

 

 

그래서 완성된 코드는 아래와 같다.

#include <iostream>
#include <string>
using namespace std;

int N;
int M[1000001];

// 개수를 담아보자

void f(int count) {
	if (count == 1 || count==2 || count==3) { // count=1,2,3이면 count와 개수가 동일
		M[count]=count;
	}
	else {
		if (M[count] == 0) { // 아직 값이 채워지지 않았다면
			M[count] = (M[count - 1] + M[count - 2]) % 15746; // 값 채워넣기
		}
	}
	if (count == N) return; // 원하는 값에 도달했다면 return
	f(count + 1); // 아니라면 count 증가시켜 N에 도달하도록 만듦
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);


	cin >> N;

	f(1);
	printf("%d", M[N]);
}