[Algorithm] 다이나믹 프로그래밍 타일링 문제 풀어보기 (2/2) (백준 2133번, 14852번 )

 

 

https://www.inflearn.com/course/algorithm-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%8B%A4%EC%8A%B5/lecture/12352

알고리즘의 개요와 실습 환경 구축 - 인프런 | 학습 페이지

 

인프런 알고리즘 강의 22강, 23강에 대한 리뷰이다.

 

 

 

 

 

1. 타일 채우기, BaekJoon #2133 (https://www.acmicpc.net/problem/2133)

 

 

 

 

 

 

 

처음 n - 2 일 때만 3개, n - 4가 2개, n - 6이 2개, ... 로 0번째 일 때까지 -짝수번째 항은 2개의 경우가 존재함.

 

그래서 식은 3 * 재귀함수(n - 2) + 2 * (n - 4) + 2 * (n - 6) ... 2 * (n - n) 이다.

 

 

 

**C++

 

 

#include <stdio.h>

int d[1001];

int dp(int x) {
	if (x == 0) return 1;
	if (x == 1) return 0; // 가로길이 1인 경우 해당 안되므로 0
	if (x == 2) return 3; // 가로 길이 2인 경우 경우의 수 3개 
	if (d[x] != 0) return d[x];
	int result = d[x] = 3 * dp(x - 2);
	for (int i = 3; i <= x; i++) {
		if (i % 2 == 0) {
			result += 2 * dp(x - i);
		}
	}
	return d[x] = result;
}

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

 

 

 

 

** Python

 

 

import sys
sys.setrecursionlimit(10**6)

d = [0] * 1001
def dp(x):
    if x == 0: return 1
    if x == 1: return 0
    if x == 2: return 3
    if d[x] != 0: return d[x]
    d[x] = 3 * dp(x - 2)
    result = d[x]
    for i in range(3, x + 1):
        if i % 2 == 0:
            result += 2 * dp(x - i)
    d[x] = result
    return d[x]


y = int(input())
r = dp(y)
print(r)

 

 

 

2. 타일 채우기 3, BaekJoon #14852 (https://www.acmicpc.net/problem/14852)

 

 

 

 

 

기본적으로 생각되는 경우의 수는

 

 

이지만

 

 

이런 경우도 존재한다.

 

 

 

 

 

따라서 식은

2 * 재귀함수(n - 1) + 3 * 재귀함수(n - 2) + 2 * 재귀함수(n - 3) + 2 * 재귀함수(n - 4) ... 2 * 재귀함수(n-n)

이다.

 

 

 

 

** C++

 

 

1) 시간 초과

 

#include <stdio.h>

int d[1000001];

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];
	int result = d[x] = 3 * dp(x - 2) + 2 * dp(x - 1);
	for (int i = 3; i <= x; i++) {
		result += 2 * dp(x - i) % 1000000007;
	}
	return d[x] = result;
}

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

 

 

2) dynamic programming 사용

 

 

2차원으로 만들어준다.

 

 

 

 

#include <stdio.h>

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]) % 1000000007;
		d[i][0] = (3 * d[i - 2][0] + 2 * d[i - 1][0] + 2 * d[i][1]) % 1000000007;
	}
	return d[x][0];
}

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

 

 

이 경우 이해가 안 갈 수도 있는데 내가 이해한 바는 이렇다. 피보나치를 예로 들면

 

1	1	2	3	5	8	13	21	34	55
		1	1	2	3	5	8	13	21

 

그래서 답이 첫째줄인 d[x][0]

 

** Python

 

런타임에러나서 조금 바꿨다

 

import sys
sys.setrecursionlimit(10**6)

d = [[0]*2 for i in range(1000001)]
def dp(x):
    d[0][0] = 0
    d[1][0] = 2
    d[2][0] = 7
    d[2][1] = 1
    for i in range(3, x + 1):
        d[i][1] = (d[i - 1][1] + d[i - 3][0]) % 1000000007
        d[i][0] += 3 * d[i - 2][0]
        d[i][0] += 2 * d[i - 1][0]
        d[i][0] += 2 * d[i][1]
        d[i][0] = d[i][0] % 1000000007
    return d[x][0]


y = int(input())
r = dp(y)
print(r)