[C++][DP - BOJ 2xn 타일링(11726,11727)] 점화식, 배열 초기화 fill_n

백준 2xn 타일링(11726)

백준 2xn 타일링2(11727)

 

 

1. 풀이

 

11726 N 번째 타일 배치는

1. N-1 번째에 2x1 타일을 붙이는 방법 (세로 타일 | 붙이기)

2. N-2 번째에 1x2 타일 2개를 붙이는 방법 (가로 타일 = 붙이기)

을 통해 만들 수 있다.

 

11726 점화식

D[n] = D[n-1] + D[n-2]

 

11727의 점화식도 11726과 크게 다르지 않다,

1. N-1 번째에 2x1 타일을 붙이는 방법 (세로 타일 | 붙이기)

2. N-2 번째에 1x2 타일 2개를 붙이는 방법 (가로 타일 = 붙이기)

3. N-2 번째에 2x2 타일 1개를 붙이는 방법 

 

11727 점화식

D[n] = D[n-1] + D[n-2]*2

 

2. 코드

11726번

//https://www.acmicpc.net/problem/11726
// BOJ 11726 2XN  
#include <iostream>
#include <cstring>
#include <algorithm>

#define N_MAX 1001

using namespace std;

int dp[N_MAX];

int bottomUp(int n){
	for(int i =3 ;i<=n;i++){
		dp[i] = (dp[i-1] + dp[i-2])%10007;
	}
	return dp[n];
}

int topDown(int n){
	if(n == 0 || n == 1)
		return 1;
	if (dp[n]>0)
		return dp[n];
	dp[n] =  (topDown(n-1)+topDown(n-2))%10007 ;
	return dp[n];
}
int main(){
	int n;
	scanf("%d",&n);
	memset(dp,0 ,sizeof(int)*(n+1));
	fill_n(dp,n+1,0); //배열 초기 
	dp[1] = 1;
	dp[2] = 2;
	printf("%d",bottomUp(n));
	return 0;
	
}

 

11727번

//https://www.acmicpc.net/problem/11727
// BOJ 11727 2XN  2
#include <iostream>
#include <cstring>
#include <algorithm>

#define N_MAX 1001

using namespace std;

int dp[N_MAX];

int bottomUp(int n){
	for(int i =3 ;i<=n;i++){
		dp[i] = (dp[i-1] + dp[i-2]*2)%10007;
	}
	return dp[n];
}
int topDown(int n){
	if(n == 0 || n == 1)
		return 1;
	if (dp[n]>0) //값 이미 찾은 경우 
		return dp[n]; 
		
	dp[n] = (topDown(n-1)+topDown(n-2)*2)%10007;	
	return dp[n];
}

int main(){
	int n;
	scanf("%d",&n);
	memset(dp,0 ,sizeof(int)*(n+1));
	fill_n(dp,n+1,0); //배열 초기 
	dp[1] = 1;
	dp[2] = 3;
	printf("%d",topDown(n));
	//	printf("%d",bottomUp(n));

	return 0;
	
}

 

 

3. c++ 배열 초기화

 

1) std::fill_n

 

fill_n(변경하려는 원소의 범위 시작 주소, 변경하려는 원소 개수, 변경값)

int arr[10]; 
fill_n(arr,10,1);

 

2) std::fill

변경하려는 원소의 범위 시작 주소, 변경하려는 원소의 범위 종료 주소, 변경값

종료 주소 쓸 때 주의 바람

 

 

참고 사이트

 

배열 초기화

배열 초기화