Boj 17216) 가장 큰 감소 부분 수열

문제

백준 17216

방법 1

설명

전형적인 DP 방법.

• DP 로 LIS 푸는 방법이랑 크게 다르지도 않음

시간 복잡도

O(N * NumRange)

코드

int inputs[1001];
pair<int, int> dp[1002];

int main()
{
	int n; 
	cin >> n;
	for (int i = 0; i < n; i++) cin >> inputs[i];

	for (int i = n-1; i >= 0; i--) // 아래 포문과 방향만 같으면 됨.
	{
		for (int j = 1001; j > 0; j--)
		{
			if (inputs[i] < j)
			{
				if(dp[j].first < inputs[i]) // 마지막수보다 작은 수가 나오면 그냥 더해줌
				{
	                dp[j].first = inputs[i];
					dp[j].second = dp[j].second + inputs[i];
				}
				else if(dp[j].second <= dp[inputs[i]].second + inputs[i])
	            {
					dp[j].first = inputs[i];                    
					dp[j].second = dp[inputs[i]].second + inputs[i];
				}
	
			}
		}
	}
	
	cout << dp[1000].second;
}

방법 2

설명

LIS 풀 때 사용하는 이분탐색을 응용한 방법.

길이가 1인 수열부터 LIS 인 수열까지 하나씩 경우를 따짐

시간복잡도가 1 + 2 + ... Len(LIS) 이럴줄 알았는데

• 7
  10 2 20 2 1 40 20
  

• 위를 넣어보면 Len(LIS) 는 3 이고 dp 에 저장된 값이 4 + 2 + 1 임
• 이게 더 느린거 같은데 시간복잡도 어케구하지.

시간 복잡도

O(\(N^2\) )

코드

#define MAX_LINE 1001
int lis[MAX_LINE], cnt = 0;
int inputs[MAX_LINE], indices[MAX_LINE];

unordered_map<int, int> dp[MAX_LINE]; 
int DFS(int p, int idx, int sum = 0)
{
	if (p == -1) return sum;

	if (dp[p].find(idx) != dp[p].end())
		return dp[p][idx] + sum;
	
	int f, fi;
	for(fi = idx; fi >= 0; fi--)
		if (indices[fi] == p)
		{
			f = inputs[fi];
			break;
		}
	
	dp[p][idx] = max(DFS(p - 1, fi - 1, sum + f), DFS(p - 1, idx, sum)) - sum;
	
	return dp[p][idx] + sum;
}

int main()
{
	int n;
	cin >> n;

	// LIS 업데이트
	for (int i = 0; i < n; i++) cin >> inputs[i];
	for (int i = 0; i < n; i++)
	{
		int *p;
		p = lower_bound(lis, lis + cnt, inputs[i], [](int a, int b) { return a > b; });
		*p = inputs[i];
		if (p - lis == cnt) cnt++;
		indices[i] = p - lis;
	}
	
	// 값 추적해서 최댓값 구하기
	cout << DFS(cnt-1, n-1);
}