두칸 뛰는 문제
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 | #include <iostream> #include <algorithm> #include <cstring> using namespace std; int grapes[10000]; int cache[10002]; int N; int getMaxGrape(int pos) { if (pos == N + 1) return 0; int & ret = cache[pos + 1]; if (ret != -1) return ret; ret = 0; for (int i = pos + 1; i < N; i++) { int twoSum = 0; for (int j = 0; j < 2; j++) { if (i + j < N) { twoSum += grapes[i + j]; ret = max(ret, getMaxGrape(i + j + 1) + twoSum); } } } return ret; } int main() { int i = 0; memset(cache, -1, sizeof(cache)); cin >> N; for(int i = 0; i < N; i++) cin >> grapes[i]; cout << getMaxGrape(-1) << endl; //system("pause"); return 0; } | cs |
'* Computer Science > Algorithm' 카테고리의 다른 글
baekjun 9251. LCS(Longest Common Sequence) (0) | 2018.08.12 |
---|---|
baekjun 1520. 내리막 길 (0) | 2018.08.09 |
baekjun 2293. 동전1 (0) | 2018.08.08 |
baekjun 10844. 쉬운 계단 수 (0) | 2018.08.06 |
baekjun 1005. ACM Craft (0) | 2018.08.06 |