(백준 11726번/11727번 2*n 타일링 C++) 라이님 블로그 대회 알고리즘 따라잡기 5) DP(Dynamic Programming) 동적계획법 2탄

기세를 몰아! 디피디피~

백준 11726번

https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

 

잘 생각해보면 n번째 케이스는 n-1 번째 케이스에서 직사각형을 세로로 세워 붙인 경우와 n-2번째 케이스에서 직사각형을 눕혀서 2개 붙인 경우의 합으로 이루어졌음을 알 수 있다.

// 백준 11726번
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <algorithm>
const long long MAX = 1001;
long long dp[MAX];

long long f(long long N) {
	if (N == 1) return 1;
	if (N == 2) return 2;
	if (dp[N] != -1) return dp[N];
	dp[N] = (f(N - 1)%10007 + f(N - 2)%10007)%10007;
	return dp[N];
}

int main() {
	long long N; scanf("%lld", &N);
	std::fill_n(dp, MAX, -1);
	printf("%lld", f(N));
	return 0;
}

틀린 이유는... 배열의 max 크기를 1001이 아닌 101로 뒀기 때문입니다..^^(문제를 잘 읽읍시다ㅠ)

 

매우 유사한 문제인 11727번!

백준 11727번

https://www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

 

11726번에서

1. Base case를 수정해주고

2. n-2번째 케이스에서 직사각형 2개를 눕혀 붙이는 경우와 더불어 정사각형을 놓는 경우도 고려해주면 된다.

// 백준 11727번
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <algorithm>
const long long MAX = 1001;
long long dp[MAX];

long long f(long long N) {
	if (N == 1) return 1;
	// 바뀐 부분 1. base case : N = 2
	if (N == 2) return 3;
	if (dp[N] != -1) return dp[N];
	// 바뀐 부분 2. f(N-2) * 2 
	dp[N] = (f(N - 1)%10007 + (f(N - 2) * 2 )%10007)%10007;
	return dp[N];
}

int main() {
	long long N; scanf("%lld", &N);
	std::fill_n(dp, MAX, -1);
	printf("%lld", f(N));
	return 0;
}