[BOJ] 1904 01타일 - 동적 계획법

BOJ 1904 01 타일 

동적 계획법을 이용해야 하는 문제이다.

이전의 답이 다음의 답을 정한다.

수열을 만들때 1 또는 00 만 선택할 수 있다.

N = 1 , N = 2 일 만들수 있는 수열은 각각 1 그리고 11,00 이다.

이제 3일때 부터가 중요하다.

 

길이가 3인 수열을 만들기 위해서는

길이가 2인 수열에 1을 추가를 하던지,

길이가 1인 수열에 00을 추가하던지, 11을 추가해야한다.

그런데 잘 생각을 해보면 길이가 1인 수열의 원소의 뒤에 11을 붙이면

경우는 길이가 2인 수열에서 1을 붙인것 과 겹친다.

 

N-2 의 원소에 11을 추가한 원소들은 N-1의 원소에 1을 추가한 원소들과 겹친다.

 

길이가 N인 수열은 길이가 N-2인 수열의 개수 + 길이가 N-1인 수열의 개수 와 같다.

WHY ?

N-1  수열에는 N-2 에서 1을 추가해 만든 수열이 포함되어 있음을 기억하자. 

따라서 N-2  수열에서는 무조건 후속타를 00으로 가져가고,

N-1 수열에서는 무조건 후속타를 1로 가져가는 것이다. 이 둘을 합치면,N인 수열의 모든 경우를 자연스럽게 구할수 있는 것이다.  

R(N) = R(N-2) + R(N-1) 을 이용해서 답을 구하면 된다.

 

답을 출력하려고 하는데,

출력 조건을 보면 답을 15746으로 나눈 나머지를 출력하라고 되어있다.

 

답에만 나머지연산을 적용하면 오답처리가 된다...

아마도 오버플로우를 방지하기 위한 조건인듯 하다.

이 경우 언제 오버플로우가 날지 모르기 때문에 나머지를 요구하는 경우는

쿨하게 모든 원소에 나머지 연산을 적용시켜도 된다.

모듈러 연산은 덧셈에 대한 분배법칙이 성립하기 때문이다.

 

모듈러 연산은 분배법칙이 성립한다.

문제를 위한 코드를 구현하면 다음과 같다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;

int Result[1000001] = { 0,1,2, };

int main()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int NumTile;

	std::cin >> NumTile;

	if (1 == NumTile)
	{
		std::cout << "1" << '\n';
		return 0;
	}

	if (2 == NumTile)
	{
		std::cout << "2" << '\n';
		return 0;
	}

	for (int i = 3; i <= NumTile; ++i)
		Result[i] = (Result[i - 2] + Result[i - 1]) % 15746;
		
	std::cout << Result[NumTile] << '\n';
	return 0;
}