* Computer Science/Algorithm

baekjun 2156. 포도주 시식

soicem 2018. 8. 8. 19:40

 두칸 뛰는 문제


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, -1sizeof(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