More actions
Mario
선형탐색을 하는 문제입니다. 재귀함수나, DynamicProgramming을 연습하는데 좋습니다. 마리오 덕후는 마리오의 목숨을 최대한으로 가지고 쿠퍼를 잡으려고 합니다. 그런데, 이 덕후는 각 판마다 목숨을 얻거나 잃는 갯수를 모두 가지고 있습니다. 그리고 마리오는 굴뚝을 통해 한판 뛰어넘을 수 있는 방법도 있습니다. 최대의 목숨을 가지러 갈때, 몇개의 목숨이 될까요?
input: 7 1 4 -4 -6 5 -3 -1 output: 5
input2: 5 1 2 3 4 5 output2: 15
input3: 4 -2 1 -4 -3 output3: -4
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;
}