Baekjoon11054-가장 긴 바이토닉 부분 수열

백준 사이트 2638 - 치즈 문제입니다.

1. 문제

https://www.acmicpc.net/problem/11054

---

2. Input , Output

---

3. 분류 및 난이도

DP문제입니다.
어려웠습니다. 백준에서는 Gold3의 난이도를 책정하고 있습니다.

---

4. 생각한 것들

• 점화식을 구하기 위해 노트에 써내려가봤습니다.
• 맨 처음 알게된 사실은 하나의 dp에 정보를 담을 수 없다는 것 입니다.
  • 어떠한 인덱스를 기준으로 이 인덱스가 커지는 수열에 포함되는게 맞는지 줄어드는 수열에 포함되는지 맞는지 생각해야합니다. -> dp2개 써야합니다.(updp, downdp)
• 2개를 쓰는건 알았지만 증가하는 수열에도 {1,2,5,5,4,5} 이런 식으로 있으면 맨 뒤에있는 5가 최대가 되는 기준이 필요했습니다.
  • 인덱스 기준으로 전에 있던 값들에 대한 dp들을 비교합니다. 커지는 수열은 ‘줄어들다가 커질 수 ‘없으므로 updp만 보면 됩니다.
• 감소하는 수열은 {5,10,4,10,3,5,1} 이런 예시가 있다고 합시다.
  • 처음에는 인덱스 기준으로 가장 가깝고 값보다 큰 것을 찾아 dp를 넣었습니다. 틀렸습니다. 위의 예제에서 맨 뒤의 1 기준으로 바로 앞 5의 dp를 넣으면 틀립니다.
  • 그래서 이것도 자신의 앞의 dp정보를 다 확인해야하는데, dp에 넣으려면 downdp 뿐만아니라 updp도 봐야합니다.
  • 다 증가하고 이제 감소하기 시작하는 부분, 감소하고 있던 경우 2가지 경우가 있기 때문입니다.
• 여담으로 input이 ‘1 1’ 들어오면 결과값은 1을 내야합니다. 이 실수에 한 번 틀렸습니다.
• 하나 더 실수할만한 사실은 맨 뒤의 값이 항상 결과값일 수 없습니다.
  • {5,4,3,2,4} 수열인 경우 맨 뒤인 ‘4’가 아닌 그 앞인 ‘2’ 기준으로 4를 도출해내야합니다.

---

5. code

#include<iostream>
#include<algorithm>
using namespace std;


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n=0;
	int result = 1;
	cin >> n;

	int* arr = new int[n + 1];
	int* dpup = new int[n + 1];
	int* dpdown = new int[n + 1];

	for (int i = 1; i <= n; ++i)
	{
		cin >> arr[i];
		dpup[i] = 1;
		dpdown[i] = 1;
	}
	
	
	for (int i = 2; i <= n; ++i)
	{
		int maxnum = 0;
		for (int j = i - 1; j > 0; --j)
		{
			//up 갱신
			//up 같은 경우는 자신보다 작은 값을 다 찾고 그 dp+1 up끼리만 해야함. 
			if (arr[i] > arr[j])
			{
				if (maxnum < dpup[j])
					maxnum = dpup[j];
			}
		}
		dpup[i] = maxnum + 1;
		maxnum = 0;
		int temp = 0;
		for (int j = i - 1; j > 0; --j)
		{
			//dpdown은 자기보다 큰 값에서 up,down비교해서 큰 값
			if (arr[i] < arr[j])
			{
				if (maxnum < max(dpdown[j], dpup[j]))// 둘중 하나보다 작으면
					maxnum = max(dpdown[j], dpup[j]);
					
			}
		}
		dpdown[i] = maxnum + 1;
		if (result < dpup[i])
			result = dpup[i];
		else if (result < dpdown[i])
			result = dpdown[i];
	}
	cout << result;
	
    delete dpup;
    delete dpdown;
    delete arr;
	return 0;
}

---

6. 후기

골드 3문제라 쫄았는데.. 쫀 만큼 좀 어려웠다. 머리 좀 아팠음.