[백준문제풀이] 15852 타일 채우기 3

 

풀이일시 : 2020-08-09

​

 

문제 :

2×N 크기의 벽을 2×1, 1×2, 1×1 크기의 타일로 채우는 경우의 수를 구해보자.

​

 

입력 :

첫째 줄에 N(1 ≤ N ≤ 1,000,000)이 주어진다.

​

 

출력 :

첫째 줄에 경우의 수를 1,000,000,007로 나눈 나머지를 출력한다.

​

 

풀이 :

다이나믹프로그래밍 DP를 이용한다

dbstndi6316.tistory.com/35?category=953970

[개념정리] DP 동적프로그래밍

가장 마지막에 오는 타일을 생각해보면

앞에 N-2개의 타일이 있는 경우 3가지

앞에 N-1개의 타일이 있는 경우 2가지 로 나눌 수 있다.

또한 3부터 하나씩 증가할 때마다 고유한 모양이 2개씩 나타난다.

D[i] = 3*d[i-2] + 2*D[i-1] + (2*D[i-3] + 2*D[i-4] + ... + 2*D[0])

 

#include <iostream>
using namespace std;
int d[1000001]; 

long long int dp(int x) {
	if (x == 0) return 1; //못채우는경우
	if (x == 1) return 2;
	if (x == 2) return 7; 
	if (d[x] != 0) return d[x];
	long long int result = 3 * dp(x - 2) + 2 * dp(x - 1); //점화식 part.1
	for (int i = 3; i <= x; i++) { //4개일때부터 하나씩 올라갈때마다 경우가 두가지씩 더들어간다
		result += 2 * dp(x - i)%100000007; //점화식 part.2
	}
	return d[x] = result%100000007;
}

int main() {
	int x;
	scanf("%d", &x);
	printf("%d", dp(x));
    return 0;
}

 

이 경우에는 O(N^2)정도의 시간복잡도가 나와 초과가 뜬다. 따라서 2차원 다이나믹프로그래밍 기법을사용한다.

 

#include <iostream>
using namespace std;

long long int d[1000001][2];

long long int dp(int x) {
	d[0][0] = 0;
	d[1][0] = 2;
	d[2][0] = 7;
	d[2][1] = 1;
	for (int i = 3; i <= x; i++) {
		d[i][1] = (d[i - 1][1] + d[i - 3][0]); //[i][1]로 뺀거는 예외를 따로 계산해주기위해서
		d[i][0] = (3 * d[i - 2][0] + 2 * d[i - 1][0] + 2 * d[i][1]); //완료된 식
	}
	return d[x][0];
}

int main() {
	int x;
	cin >> x;
	printf("%lld", dp(x));
}