가장 긴 바이토닉 부분 수열 (feat. 백준, 11054번)

가장 긴 바이토닉 부분 수열
https://www.acmicpc.net/problem/11054

11054번: 가장 긴 바이토닉 부분 수열

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/11054
#include <iostream>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(), cout.tie();
	register int N, arr[1001], up_dp[1001] = { 0 }, down_dp[1001] = { 0 }, ans = 0;
	cin >> N;
	up_dp[1] = down_dp[N] = 1;
	for (register int i = 1; i <= N; ++i)
		cin >> arr[i];
	for (register int i = 2; i <= N; ++i) {
		for (register int j = 1; j <= i; ++j) {
			if (arr[j] < arr[i])
				up_dp[i] = max(up_dp[i], up_dp[j]);
			if (arr[N - j + 1] < arr[N - i + 1])
				down_dp[N - i + 1] = max(down_dp[N - i + 1], down_dp[N - j + 1]);
		}
		++up_dp[i], ++down_dp[N - i + 1];
	}
	for (register int i = 1; i <= N; ++i)
		ans = max(ans, up_dp[i] + down_dp[i]);
	cout << ans - 1 << endl;
	return 0;
}
// *&)*@*

1. 예제를 기준으로 설명을 해보겠습니다.
2. 가장 앞부터 시작하여 1은 비교할 대상이 없으므로 자기자신만 해당하여 1을 가집니다.
3. 5는 가장 가까운 이전중에서 1보다 크기 때문에 1에 있던 1을 가져가고 자기자신인 5를 더해서 2를 가집니다.
4. 2는 가장 가까운 이전중에서 1보다 크기 때문에 1에 있던 1을 가져가고 자기자신인 2를 더해서 2를 가집니다.
5. 1은 비교할 대상이 없으므로 자기자신만 해당하여 1을 가집니다.
6. 4는 가장 가까운 이전중에서 2보다 크기 때문에 2에 있던 2를 가져가고 자기자신인 4를 더해서 3를 가집니다.
7. 3는 가장 가까운 이전중에서 2보다 크기 때문에 2에 있던 2를 가져가고 자기자신인 3를 더해서 3를 가집니다.
8. 4는 가장 가까운 이전중에서 3보다 크기 때문에 3에 있던 3을 가져가고 자기자신인 4를 더해서 4를 가집니다.
9. 5는 가장 가까운 이전중에서 4보다 크기 때문에 4에 있던 4를 가져가고 자기자신인 5를 더해서 5를 가집니다.
10. 2는 가장 가까운 이전중에서 1보다 크기 때문에 1에 있던 1을 가져가고 자기자신인 2를 더해서 2를 가집니다.
11. 1은 비교할 대상이 없으므로 자기자신만 해당하여 1을 가집니다.
12. 따라서 순서대로 1 2 2 1 3 3 4 5 2 1 을 갖게 됩니다.
13. 마찬가지로 뒤에서부터도 동일하게 계산하면 1 5 2 1 4 3 3 3 2 1 을 갖게 됩니다.
14. 여기서 인덱스간 서로 더했을때 가장 큰 값은 5 + 3 으로 8 입니다.
15. 하지만 문제에서 주어진 Sk인 5가 두번 포함되었으므로 1을 빼줍니다.