백준 11726 2xn 타일링(C++)

 

2*n 크기의 직사각형에

1*2 세로로 긴 직사각형과 2*1 가로가 긴 직사각형으로 채울 수 있는 방법을 우선 찾는다.

2*n에서 n이 커질수록 가로로 한칸이 길어진다. 채울 수 있는 것은 1*2나 2*1 사각형이므로

가로가 한칸 길어지면 1*2를 하나 넣을 수 있다.

3에서 4로 넘어갈때 파란색 테두리를 친 사각형들이 그 예시.

 

가로 길이가 n-2 인 경우에서 2*1을 위아래로 하나씩 배치해서  가로길이 n을 만드는 경우도 존재한다.

(초록색테두리)

 

가로 길이가 n인 직사각형은 n-1길이의 직사각형갯수와 n-2길이의 직사각형 갯수를 합한 값이라는 결과 추론 가능.

피보나치 수열의 형태를 띄고 있으므로 dp 사용.

#include <iostream>
#include <algorithm>
#include<cmath>
using namespace std;
long long dp[1001];
long long arr[1001];
int num;
int main()
{
	cin >> num;
	dp[0] = 1;
	dp[1] = 2;
	dp[2] = 3;
	for (int i = 3; i < num; i++)
	{
		dp[i] =dp[i - 2] + dp[i - 1];
	} 
	cout << dp[num - 1]%10007 << endl;

}

라고 풀면 틀린다.

num이 1000까지 입력될 수 있으므로 값이 너무 커진다.

중간중간 미리 나머지를 구해두자. (나머지 분배법칙) 활용

 

(A+B)%C = ((A%C)+(B%C))%C   (+가 곱셈이 되어도 동일 적용)

 

 

https://velog.io/@choihocheol/%EB%AA%A8%EB%93%88%EB%A1%9C-%EC%97%B0%EC%82%B0Modular-Arithmetic

모듈러 법칙을 잘 정리해두신 블로그를 첨부합니다.

 

dp[i-2]+dp[i-1] % 10007 하고 있는 것이므로 좌변의 형태였던 것을 우변의 형태로 사용하기 위해

for문 내부에서 dp[i] 값을 넣어준 뒤 10007로 나눈 나머지로 변경해준다.

#include <iostream>
#include <algorithm>
#include<cmath>
using namespace std;
long long dp[1001];
long long arr[1001];
int num;
int main()
{
	cin >> num;
	dp[0] = 1;
	dp[1] = 2;
	dp[2] = 3;
	for (int i = 3; i < num; i++)
	{
		dp[i] =dp[i - 2] + dp[i - 1];
		dp[i] %= 10007;
	} 
	cout << dp[num - 1]%10007 << endl;

}

정답 인정된 코드