[BAEKJOON] 1904번 01 타일

문 제

 

 

소 스  코 드

#include <iostream>

constexpr int NUMBER{ 15'746 };

int main() {
	int N;

	std::cin >> N;


	int  temp		{ 0 };
	int  first		{ 2 }; // 2 : 1 0
	int  second		{ 1 }; // 1 : 1

	if (1 == N) {
		std::cout << second;
		return 0;
	}
	else if (2 == N) {
		std::cout << first;
		return 0;
	}
	else {
		for (int i = 2; i < N; ++i) {

			temp = first;
			first = (first + second) % NUMBER;
			second = temp;
		}

		std::cout << first;

		return 0;
	}
}

 

풀 이

 

3  1  1 1 1  0 0 0  0 1

4 1  1 1 1 1  1 0 0 1  0 0 1 0  0 1 1 0  0 0 0

5 1  1 1 1 1 1  1 1 0 0 1  1 0 0 1 1  0 0 1 1 1  0 0 0 0 0  0 1 1 1 0  0 1 0 0 0  0 0 0 1

6 1  1 1 1 1 1 1  1 1 1 0 0 1  1 1 0 0 1 1  1 0 0 1 1 1  1 0 0 0 0 1  0 0 1 1 1 1  0 0 1 0 0 1  0 0 0 0 1 0  0 1 1 1 1 0  0 1 1 0 0 0  0 1 0 0 1 0  0 0 0 1 1 0  0 0 0 0 0

7 1  1 1 1 1 1 1 1  1 1 1 1 0 0 1  1 1 1 0 0 1 1  1 1 0 0 1 1  1  1 1 0 0 0 0 1  1 0 0 1 1 1 1  1 0 0 1 0 0  1  1 0 0 0 0 1 1  0 0 1 1 1 1 1  0 0 1 1 0 0 1  0 0 1 0 0 1 1  0 0 0 0 1 1 1  0 0 0 0 0 0 0  0 1 1 1 1 1 0  0 1 1 1 0 0 0  0 1 1 0 0 1 0  0 1 0 0 1 1 0  0 1 0 0 0 0 0  0 0 0 1 1 1 0  0 0 0 1 0 0 0  0 0 0 0 0 1

• 위의 표를 보면 앞에 1이 들어 간 경우 첫번째 1을 제외한 나머지가 N - 1 번째 와 같고 0 일 경우 N - 2 번째와
  같은 것을 알수 있다. 피보나치 수열과 같다.
  ex ) 7의 경우 맨 앞에 1이 있는 경우 6과 동일 하고 맨 앞에 0 이있을 경우 5와 동일 하다.

• 숫자의 자릿수가 20개를 넘어가기 때문에 표현할 수 있는 방법이 없다. 하지만 조건에 나머지가 있기 때문에 나머지로 한다면 이상 없이 구현이 가능하다.

 

실 수 했 던  점

 

#include <iostream>

constexpr int NUMBER { 15'746 };

void Func(int, int, int&);

int main() {
	int N;

	std::cin >> N;

	
	int share	{ ( N / 2 ) + 1 };
	int temp	{ 0 };	

	for (int i = 0; i < share ; ++i) {
		Func(N - i, i, temp);
	}

	temp = temp % NUMBER;
	std::cout << temp;

	return 0;
}

void Func(int one, int twozeros, int & ref_temp) {
	
	int 	temp		{ 1 };
	int	con_under	{ twozeros };

	for (int i = 0; i < twozeros; ++i) {
		temp *= one--;
		temp /= con_under--;
	}
	ref_temp += temp;
}

 

• for문에서 00이 들어갈 수 있는 수를 통하여 자리에 00이 들어갈 수 있는 경우의 수를 통하여 구현하려 하였지만, 시간 초과라는 비효율적인 방법이기 때문에 실패하였다.

 

결 과 값

 

 

문 제  출 처

문제 링크 : [ BAEKJOON ] : https://www.acmicpc.net/problem/1904