광그로

https://www.acmicpc.net/problem/11054 가장 긴 증가 수열에 대하여 arr[0]~arr[i] 까지, 역순으로 arr[i]~arr[0]에 대하여 구하고, 각각의 값을dp[i].first와 dp[i].second에 저장, dp 배열 first와 second의 합의 최대값을 구합니다. 123456789101112131415161718192021222324252627282930313233343536373839#include using namespace std; int arr[1001];pair dp[1001];int main(){ int n; cin >> n; for (int i = 0; i > arr[i]; } for (int i = 0; i

https://www.acmicpc.net/problem/11722 11053 가장 긴 부분 수열을 조금 수정한 문제입니다. 123456789101112131415161718192021222324252627#include using namespace std; int arr[1001];int dp[1001];int main(){ int n; cin >> n; for (int i = 0; i > arr[i]; } for (int i = 0; i dp[i]) { dp[i] = dp[j] + 1; } } } int result = 0; for (int i = 0; i

https://www.acmicpc.net/problem/2156 9465스티커 문제와 유사한 접근 [1] [2] [3] [4] [5] [6] 안마심 0 6 6+10 첫번째잔 6 10 6+13 두번째잔 0 6 +10 10+13 1234567891011121314151617181920212223242526272829#include #include using namespace std; int content[10001];int dp[10001][3]; int max(int a, int b, int c) { return max(max(a, b), c);}int main(){ int n; cin >> n; for (int i = 1; i > content[i]; } dp[0][0] = dp[0][1] = dp[0..

https://www.acmicpc.net/problem/9465 1234567891011121314151617181920212223242526272829303132333435363738#include #include using namespace std; long long sticker[100001][2];long long dp[100001][3];//[열][] 0 : 뜯지 않음 1 : 1열 뜯음 2 : 2열 뜯음 int main(){ int test; int n; cin >> test; long long input; while (test--) { cin >> n; for (int i = 1; i > sticker[i][0]; } for (int i = 1; i > sticker[i][1]; } dp[0..

https://www.acmicpc.net/problem/2193 1 1 0 1 10 0/1 2 100 0/1 3101 0 1000 0/151001 01010 0/1 2+1+2+2+1 8 12345678910111213141516#include using namespace std;long long dp[91]; int main(){ dp[1] = 1; dp[2] = 1; int n; cin >> n; for (int i = 3; i

https://www.acmicpc.net/problem/10844 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include #include using namespace std; //다시보기 long long dp[101][10];#define MOD 1000000000 int main(){ int n; cin >> n; for (int i = 1; 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크기가 작은 문제부터 차례대로 푼다->크기를 조금씩 키워가며 푼다->...->최초문제를 푼다