사탕 줍기 대회

---

문제풀이

1. 조건이 상당히 복잡해보인다. M개 줄, N개의 요소 라고 용어를 정리하고 들어가자.
2. k번째 줄을 선택하면 위아래 줄은 그대로 없어진다. 즉 M개줄 중에서 가장 많이 선택해도 M/2개를 넘을수 없다.
3. N개의 요소중 가장 많이 선택하는 방법은 N이 짝수일때 N/2개, 홀수일때 N/2+1개이다.
4. i개의 요소중 합이 가장크게 선택하는 방법을 dp[i]이라고 하자.
5. dp[i]은 i번째요소를 선택했을경우 dp[i-2]+number, 선택하지 않은경우 dp[i-1]의 합이다.
6. 따라서 M개의 줄은 각 그 줄에 해당하는 조건합을 구할수 있다. dp[i]=max(dp[i-1]+number, dp[i-1])이다. // k번째 줄을 선택했을때 그 줄에서 얻을수 있는 최대 사탕개수
   7.그러면 M개의 숫자로 조건이 정리된다. 각 숫자는 각줄에서 얻을수 있는 최대 사탕개수를 뜻한다.
7. 연속해서 같은줄을 선택할수 없으므로 여기서 다시 dp를 쓴다. 조건은 동일하므로 dp2[i]=max(dp2[i-1]+number, dp2[i-1])이다.

---

실제 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <math.h>
#include <string>
#include <string.h>
#include <set>

using namespace std;
#define endl "\n"


#define MAX 100000+1
int M, N;
int rowSum[MAX];
int dp[MAX];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	//ifstream cin; cin.open("input.txt");

	while (true)
	{
		cin >> M >> N;
		if (M==0 && N==0)
		{
			break;
		}

		for (int i = 1; i <= M; i++)
		{
			for (int j = 1; j <= N; j++)
			{
				int number;
				cin >> number;

				if (j == 1)
				{
					dp[j] = number;
				}
				else {
					dp[j] = max(dp[j - 1], number + dp[j - 2]);
				}
			}
			rowSum[i] = dp[N];
		}
		memset(dp, 0, sizeof(dp));

		for (int j = 1; j <= M; j++)
		{
			int number = rowSum[j];
			if (j == 1)
			{
				dp[j] = number;
			}
			else {
				dp[j] = max(dp[j - 1], number + dp[j - 2]);
			}
		}

		cout << dp[M] << endl;
	}
}