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

 

 

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

 

 

 

1. 2xn 타일링, BaekJoon #11726

 

백준 dynamic programming 관련 문제 (https://www.acmicpc.net/problem/11726)

 

참고로 이 문제는 프로그래머스에도 있다. (https://programmers.co.kr/learn/courses/30/lessons/12900)

 

 

 

 

 

가로 길이가 1인 직사각형이 붙는 마지막 항은 n - 1 이고

가로 길이가 2인 직사각형이 붙는 마지막 항은 n - 2 이다.

 

이를 이용하면 재귀함수(n -1) + 재귀함수(n - 2) 를 리턴하면 된다.

 

 

** C++

 

#include <stdio.h>

int d[1001];

int dp(int x) {
	if (x == 1) return 1;
	if (x == 2) return 2;
	if (d[x] != 0) return d[x];
	return d[x] = (dp(x - 1) + dp(x - 2)) % 10007;
}

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

 

 

** Python

 

1) (근데 런타임에러남)

 

d = [0] * 1001
def dp(x):
    if x == 1: return 1
    if x == 2: return 2
    if d[x] != 0: return d[x]
    d[x] = (dp(x - 1) + dp(x - 2))
    return d[x] % 10007


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

 

2)

 

import sys
sys.setrecursionlimit(10**6)

d = [0] * 1001
def dp(x):
    if x == 1: return 1
    if x == 2: return 2
    if d[x] != 0: return d[x]
    d[x] = (dp(x - 1) + dp(x - 2)) % 10007
    return d[x]


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

참고: https://kkkkhd.tistory.com/528

 

 

 

2. 2xn 타일링 2, BaekJoon #11727 (https://www.acmicpc.net/problem/11727)

 

 

 

 

 

 

 

가로 길이가 1인 직사각형이 오는 경우 마지막 항은 n - 1이고

가로 길이가 2이고 세로 길이가 1인 직사각형이 오는 경우 마지막 항이 n - 2,

가로 길이 2, 세로 길이 2가 2인 정사각형이 오는 경우 마지막 항이 n - 2 가 된다.

 

리턴 값은 재귀함수(n - 1) + 2 * 재귀함수 (n - 2) 이다.

 

 

 

** C++

 

#include <stdio.h>

int d[1001];

int dp(int x) {
	if (x == 1) return 1;
	if (x == 2) return 3;
	if (d[x] != 0) return d[x];
	return d[x] = (dp(x - 1) + 2 * dp(x - 2)) % 10007;
}

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 == 1: return 1
    if x == 2: return 3
    if d[x] != 0: return d[x]
    d[x] = (dp(x - 1) + 2 * dp(x - 2)) % 10007
    return d[x]


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