[Codeground 31번] 프리랜서

문제 출처 :

https://www.codeground.org/practice/practiceProblemList

알고리즘 분석 :

문제 해결에 필요한 사항

1. Dynamic Programming

2. 점화식 세우는 방법

문제를 풀기 위해 점화식을 구성해야 한다.

우선 1일째의 DP값은 a의 1일째 값 혹은 b의 1일째 값이 될 것이고

2일째 DP값은 a의 1일째 + a의 2일째 값 혹은 b의 1일째 + a의 2일째 값 혹은 b의 2일째값 중 최댓값이 될 것이다.

이렇게 구한 후 문제의 요구사항에 맞게 dp 점화식을 생각해보면

dp[i] = max(dp[i-2] + b[i], dp[i - 1] + a[i])로 구성 할 수  있게 된다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

#include <iostream> #include <cstdio> #include <memory.h> #include <algorithm>   using namespace std;   int a[10002]; int b[10002]; int dp[10002];   int main() {     int tcase;     scanf("%d", &tcase);       for (int tc = 1; tc <= tcase; tc++)     {         int n;         scanf("%d", &n);           memset(a, 0, sizeof(a));         memset(b, 0, sizeof(b));         memset(dp, 0, sizeof(dp));           for (int i = 1; i <= n; i++)             scanf("%d", &a[i]);         for (int i = 1; i <= n; i++)             scanf("%d", &b[i]);           dp[1] = max(a[1], b[1]);         dp[2] = max({ a[1] + a[2],b[1] + a[2], b[2] });           for(int i = 3; i <= n; i++)             dp[i] = max(dp[i - 2] + b[i], dp[i - 1] + a[i]);           printf("Case #%d\n%d\n", tc, dp[n]);     }       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus