Mario ¶

��형탐�� 하�� . ��함��, DynamicProgramming�� 하�� .
�� 한�� 합��. ��, �� 했�� Stage�� 항�� 합��. ��, �� 한�� 통해 �� 한 Stage�� 할 �� .(1��->3��, 3->5�� , 횟��한 ��) �� 합��.(�� Stage�� 합��) ��, �� ?

input1:
5
1 2 3 4 5
output1: 15

input2:
4
-2 1 -4 -3
output2: -4

input3:
3
2 -3 4
output3: 6

input4:
7
1 4 -4 -6 5 -3 -1
output4: 5

judge할 �� 트�� (�� ) �� , 확��해�� .

�� (�� ):

#include <stdio.h>

int bigsum=0;
int mario(int arr[],int n,int k,int sum);

int main()
{
    int i,j,n,k=0,sum=0;
    int arr[100];
    
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d",&arr[i]);
        bigsum+=arr[i];
    }
    
    mario(arr,n,k,sum);
    printf("%d",bigsum);
    
    return 0;
}

int mario(int arr[],int n,int k,int sum)
{
    if(k==n-1){
        if(sum+arr[k]>bigsum){
            bigsum=sum+arr[k];
        }
        return 0;
    }else if(k==n-2){
        mario(arr, n, k+1,sum+arr[k]);
        return 0;
    }

    mario(arr, n, k+1,sum+arr[k]);
    mario(arr, n, k+2,sum+arr[k]);
    
    
    return 0;
}