GaGe

알고리즘 과제 PA4 본문

알고리즘/[2020] 알고리즘 과제

알고리즘 과제 PA4

Sorrel 2021. 1. 9. 16:06
#include "maxSum.h"

// DO NOT modify constuctor and distructor...

maxSum::maxSum(int n, int* m){
	int i=0;
	if(!m)	return;

	num = n;
	money = new int[n];

	for(i=0;i<n;i++){
		money[i] = m[i];
	}
	return;
}

maxSum::~maxSum(){
	if(money){
		delete[] money;
	}
	return;
}

int maxSum::max(void)
{
	int r=0;
// Insert source code here...
// top - down 방식을 활용해서 짜라
	
	int p[num+1][3] = {0};
    r=findMax(num, 0, p);
	int max=0;
	for(int i = 0; i<num ;i++)
	{
		for(int j = 0; j<3 ; j++
		){
			if(p[i][j]>max)
			{
				max = p[i][j];
			}
		}
	}

	return max;
}

int maxSum::findMax(int number, int cnt, int p[][3])
{
	// 종료조건

	if(number<0)
	{
		return 0;
	}
	if(p[number][cnt])
	{
		return p[number][cnt];
	}

	if(cnt ==2) //두번 연속 마셨다면
	{
		p[number][cnt] = findMax(number-1,0,p); //그다음으로 그냥 넘어감
	}
	else if(cnt == 1 or cnt == 0) //마시거나 마시지 않거나 중에 고르기
	{
		p[number][cnt] = mmax(findMax(number-1,cnt+1,p)+this->money[number], findMax(number-1,0,p));
	}



	return p[number][cnt];


	
}

int maxSum::mmax(int a, int b)
{
	if(a<b)
	{
		return b;
	}
	else
	{
		return a;
	}
}

// Define additional functions here if you declared in maxSum.h ...

'알고리즘 > [2020] 알고리즘 과제' 카테고리의 다른 글

알고리즘 과제 PA3  (0) 2021.01.09
알고리즘 과제 PA2  (0) 2021.01.09
알고리즘 과제 PA1  (0) 2021.01.09
알고리즘 과제 PA5  (0) 2021.01.09
Comments