[BOJ]2643 : 색종이 올려 놓기(c++)

[문제] : https://www.acmicpc.net/problem/2643

[풀이]

색종이의 두 변의 길이가 1000보다 작다는 점을 이용해 배열에 {1000,1000}을 넣고 시작하였다. cache[i] = i번째 색종이 위에 올릴수 있는 색종이의 최대 갯수 + 1 이다. 반복문으로 자기 자신 위에 올릴수 있는 색종이중 최대값 찾고 +1 을 하여 리턴되게 하였다. 처음에 {1000, 1000} 을 0번 인덱스로 넣었기 때문에 반복문을 돌리지 않고 cache[0] - 1로 답을 바로 찾을 수 있다.

[코드]

#include <iostream>
#include <vector>
#include <string.h>
#include <algorithm>

using namespace std;

int cache[101];
vector<pair<int, int>> Arr;
int N;

int DP(int src)
{
	int& ret = cache[src];

	if (ret != -1)
	{
		return ret;
	}

	int k = 0;
	for (int i = 0; i <= N; ++i)
	{
		if (i == src) continue;

		if ((Arr[src].first >= Arr[i].first && Arr[src].second >= Arr[i].second) ||  
                            (Arr[src].second >= Arr[i].first && Arr[src].first >= Arr[i].second))
		{
			k = max(k, DP(i));
		}
	}

	if (k == 0) return ret = 1;
	else
		return ret = k + 1;

}

int main(void)
{
	memset(cache, -1, sizeof cache);
	cin >> N;
	Arr.push_back({ 1000,1000 });
	for (int i = 0; i < N; ++i)
	{
		int a, b;
		cin >> a >> b;

		Arr.push_back({ a,b });
	}

	DP(0);

	cout << cache[0] - 1 << endl;
}