[BOJ-2156]포도주 시식

아 이거 1년전에도 풀었었구나..

연속된 수열이 있을 때 

수의 크기는 포도주 양을 뜻하며, 포도주를 가장 많이 마셔야 한다. (= 선택한 수들을 가장 크게 만들어야 한다.)

수열을 선택할 때 조건이 1가지 있다. 

연속된 수 3개는 선택할 수 없다. 이 문장의 의미는 ...XOOX.. , ..XOX.. 는 가능하며, XOOOX 인 경우는 불가능 하다는 의미임.

[입력]

n

a1 

a2 

.. 

an-1 

an

입력으로 수열의 갯수가 주어지고,

수가 차례대로 주어진다.

[출력]

위 문제 조건을 따라서 가장 큰 합을 출력한다.

[접근방법]

0잔 마셨을 경우,

1잔 마셨을 경우,

2잔 마셨을 경우 로 나누어 생각했음.

0잔 마셨을 경우는 현재 수열 input[i] 를 선택하지 않고, 

이전[i-1]에 0잔마셨을 경우, 1잔, 2잔 에서 최대값을 찾는다. 

왜냐하면 어차피 마시지 않는 경우면 이전에 0,1,2잔 을 마셔도 상관이 없기 때문임.

1잔 마셨을 경우는 이전 0잔 마셨을 때 + input[i] 을 한다. 

2잔 마셨을 경우는 1잔 마셨을 경우 + input[i]를 한다. 

그러면 이 중에서 최대 값이 나올 때를 ans 로 값을 넣어주면 된다.

 

#include<cstdio>
#define din1(a) scanf("%d", &a)
 
const int MAX = 111111;
int n;
int ans;
int dp[3][MAX];
int input[MAX];
int max2(int a, int b) { return (a > b) ? a : b; }
int max3(int a, int b, int c) { return max2(a, max2(b, c)); }
int main() {
    
    din1(n);
    // 0 1 2 init
    for (int i = 3; i < n + 3; i++) { 
        din1(input[i]);
        dp[0][i] = max3(dp[1][i-1], dp[2][i-1], dp[0][i-1]);
        dp[1][i] = dp[0][i - 1] + input[i];
        dp[2][i] = dp[1][i - 1] + input[i];
        ans = max3(dp[0][i], dp[1][i], dp[2][i]);
    }
    printf("%d\n", ans);
    return 0;
}

#2156
 
step=[[0,0,0],[0,0,0],[0,0,0]]
res = 0
T=int(input())
for x in range(T):
    s=int(input())
    step[0].append(s)
    if(s==0):
        step[1].append(max(step[1][2+x],step[2][2+x]))
        step[2].append(max(step[1][2+x],step[2][2+x]))
    elif(x<=2):       
        step[1].append(max(max(step[1][:x+1]),max(step[2][:x+1]))+step[0][2+x]+step[0][3+x])
        step[2].append(max(max(step[1][:x+2]),max(step[2][:x+2]))+step[0][3+x])
    else:
        step[1].append(max(max(step[1][x-3:x+1]),max(step[2][:x+1]))+step[0][2+x]+step[0][3+x])
        step[2].append(max(max(step[1][x-3:x+2]),max(step[2][:x+2]))+step[0][3+x])
    if(res < step[1][3+x]): res = step[1][3+x]
    if(res < step[2][3+x]): res = step[2][3+x]
print(res)
 
#10 977 200 517 851 23 662 880 815 26 214
#6 1 1 0 0 1 1