Mario ¶
- 선형탐색을 하는 문제입니다. 재귀함수나, DynamicProgramming을 연습하는데 좋습니다.
- 마리오 덕후는 마리오의 목숨을 최대한으로 가지고 쿠퍼를 잡으려고 합니다. 그런데, 이 덕후는 게임을 너무 여러번 했더니 각 Stage에서 목숨을 얻거나 잃는 갯수가 항상 일정합니다. 또, 이 덕후는 모든 지름길을 다 알고 있어 원한다면 굴뚝을 통해 마리오를 한 Stage를 건너뛰게 할 수 있습니다.(1탄->3탄, 3->5탄 등, 횟수제한 없음) 이 덕후는 가장 많은 목숨을 얻은 채로 게임을 끝내고 싶어합니다.(마지막 쿠퍼가 나오는 Stage는 꼭 들러야합니다) 이때, 이 덕후는 몇 개의 목숨으로 게임을 끝낼 수 있을까요?
5
1 2 3 4 5
output1: 15
input2:
4
-2 1 -4 -3
output2: -4
4
-2 1 -4 -3
output2: -4
input3:
3
2 -3 4
output3: 6
3
2 -3 4
output3: 6
input4:
7
1 4 -4 -6 5 -3 -1
output4: 5
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; }