광그로

https://www.acmicpc.net/problem/9095 123456789101112131415161718192021222324#include using namespace std; int dp[12]; int main(){ int test; cin >> test; int n; dp[1] = 1; dp[2] = 2; dp[3] = 4; for (int i = 4; i > n; cout

https://www.acmicpc.net/problem/11727 1234567891011121314151617#include using namespace std; int main(){ int dp[1001]; dp[1] = 1; dp[2] = 3; int n; cin >> n; for (int i = 3; i

https://www.acmicpc.net/problem/11726 12345678910111213141516171819202122#include #include #include using namespace std;int dp[1001]; //2xn 직사각형을 채우는 방법의 수 int function(int n) { if(!dp[n]) dp[n] = ( function(n-1) + function(n-2) ) % 10007; return dp[n];}int main(){ int n; cin >> n; memset(dp, 0, sizeof(dp)); dp[1] = 1; dp[2] = 2; function(n); cout

https://www.acmicpc.net/problem/1463 1234567891011121314151617181920212223242526#include #include #include using namespace std;#define INF 9999999 int dp[1000001]; : Memoization void divide(int x, int cnt) { if (dp[x] > t; memset(dp, INF, sizeof(dp)); divide(t, 0); cout

다이나믹 프로그래밍의 속성1. Overlapping Subproblem: 최초문제를 작은 문제로 쪼갤 수 있으며, 큰 문제와 작은 문제를 동일한 방법으로 풀 수 있다.2. Optimal Substructure: 문제의 정답을 작은 문제의 정답에서 도출할 수 있다. 작은 문제의 정답을 구했다면, 그 정답을 어딘가(배열)에 메모를 한다. : Memoization 다이나믹 프로그래밍의 풀이법1. Top-down작은 문제로 나눈다->작은 문제를 푼다->최초문제를 푼다재귀호출2. Bottom-up크기가 작은 문제부터 차례대로 푼다->크기를 조금씩 키워가며 푼다->...->최초문제를 푼다