[백준] 11726번 - 2xn 타일링 (파이썬/C++) 문제 및 풀이

문제) 백준 - 동적 계획법(Dynamic Programming) - 2xn 타일링

-> www.acmicpc.net/problem/11726

11726번: 2×n 타일링

 

점화식을 다음과 같이 작성할 수 있다.

f(n) = f(n - 1) + f(n - 2)

파이썬 소스 코드는 위 점화식을 이용해서 작성했고, C++에서는 기저 사례(n = 1, n =2)의 설정과 재귀를 통해 답을 계산한다.

 

 

 

파이썬 소스코드)

	import sys
	n = int(sys.stdin.readline())
	dp = [0, 1, 2]
	for i in range(3, n+1):
	dp.append((dp[i-1] + dp[i-2]) % 10007)
	print(dp[n])

view raw 11726.py hosted with ❤ by GitHub

 

 

C++ 소스코드)

	#include <bits/stdc++.h>
	#define endl "\n"
	using namespace std;
	int cache[1001];
	int solve(int n) {
	if (n == 1) return 1;
	if (n == 2) return 2;
	int& ret = cache[n];
	if (ret != -1) return ret;
	return cache[n] = (solve(n - 1) % 10007 + solve(n - 2) % 10007) % 10007;
	}
	int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	memset(cache, -1, sizeof(cache));
	int n; cin >> n;
	cout << solve(n) << endl;
	return 0;
	}

view raw 11726.cpp hosted with ❤ by GitHub