DP2 C++ 백준 BOJ 11726 2 x n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하는 문제입니다. 자주 접할 수 있는 DP문제(다이나믹 프로그래밍) 유형입니다. 보통 DP문제는 피보나치 수열, 재귀함수 등을 이용하여 해결 가능합니다. 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net #include using namespace std; int dp[1001]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int num; cin >> num;.. 2022. 12. 19. [기초] 다이나믹 프로그래밍(Dynamic Programming, DP) 다이나믹 프로그래밍 큰 문제를 작은 문제로 나눠서 푸는 알고리즘으로 동적 계획법이라고도 합니다. 동적 계획법 - 위키백과, 우리 모두의 백과사전 ko.wikipedia.org 아래 두 가지 속성을 만족해야 다이나믹 프로그래밍으로 문제를 풀 수 있습니다. 1. Overlapping Subproblem : 겹치는 부분 문제 2. Optimal Substructure : 문제의 정답을 작은 문제의 정답에서 구할 수 있을 때 Overlapping Subproblem 겹치는 작은 부분 문제로 나눠서 푸는 것이 핵심입니다. 문제 작은 문제 - 작은 문제 (두 작은 문제가 겹쳐야 됨) 먼저 피보나치 수를 예시로 들어 알아보면, - 피보나치 수 - F(0) = 0 F(1) = 1 F(n) = F(n-1) + F(n-2.. 2022. 7. 27. 이전 1 다음
