분류 전체보기52 13398. 연속합2 1. 해결방법 Dynamic Programming DP[n] : n번째 수를 포함했을 때 연속합의 최대합을 의미. DP_left[n] : n번째 수를 포함했을 때 n 기준 왼쪽에 있는 연속합의 최대합을 의미. DP_right[n] : n번째 수를 포함했을 때 n 기준 오른쪽에 있는 연속합의 최대합을 의미. 문제의 조건에는 "수열에서 수를 하나 제거할 수 있다 (제거하지 않아도 된다)" 라고 하였기 때문에, n을 기준으로 왼쪽과 오른쪽에 있는 연속합을 더할 수 있다. DP_left[n - 1] + DP_right[n + 1] 수를 제거하지 않았을 때의 연속합의 최대합과, 수를 하나 제거했을 때의 연속합의 최대합을 비교하면 된다. 2. Solution #include #define MAX_ 100000 +.. 2022. 8. 20. 2193. 이친수 1. 해결방법 Dynamic Programming DP[n] : n자리 수 이친수 개수를 의미 DP[1] = 1 DP[2] = 1 DP[3] = 2 DP[n] = DP[n-1] + DP[n-2] 2. Solution // Dynamic Programming #include #define MAX 90 + 1 #define endl "\n" typedef long long ll; using namespace std; ll N; ll DP[MAX]; void Input() { cin >> N; } void Initial() { DP[0] = 0; DP[1] = 1; DP[2] = 1; } void Solution() { for (int i = 3; i 2022. 8. 17. 2156. 포도주 시식 1. 해결방법 Dynamic Programming DP[n] : n번째까지 마신 포도주 최대 양을 의미 DP[1] = juice[1] = 0 DP[2] = juice[1] + juice[2] DP[3] = ??? DP[3] 은 juice[1] + juice[3] OR juice[2] + juice[3] OR DP[2] DP[n] = ??? DP[n] 은 DP[n-1] OR DP[n - 2] + juice[n] OR DP[n - 3] + juice[n - 1] + juice[n] 2. Solution // Dynamic Programming #include #include #define MAX 10000 + 1 #define endl "\n" using namespace std; int n, answer .. 2022. 8. 17. 1932. 정수 삼각형 1. 해결방법 Dynamic Programming 문제이다. N[floor][a] :: floor층의 a 번째 값을 저장한다. (0 N[i][j]; } } } void Solution() { DP[0][0] = N[0][0]; for(int i = 1; i < n; i++) { for(int j = 0; j 2022. 8. 10. 이전 1 2 3 4 5 6 ··· 13 다음
