(C++) 백준 11054 가장 긴 바이토닉 부분수열

1. 필요한 개념

- 동적계획법(뇌피셜로 작성하였음.. )

동적계획법은 뒤의 사건이 앞의 사건에 영향을 받을때 이용된다

그래서 동적계획법 문제는 점화식으로 풀리는 문제가 많다.. 

 

2. 문제 

 

3. 풀이

문제가 복잡해 보이지만 따지고 보면

 

1. 앞에서부터 봤을때 증가하는 수열

+

2. 뒤에서부터 봤을때 증가하는 수열

----------------------------------------

=앞에서부터는 증가하고 뒤로는 감소하는 수열

을 찾을 수 있는 원리이다. 

 

그래서 나는 앞에서 부터 증가하는 수열을 Icache에 담고 뒤에서부터 증가하는 수열을 Dcache에 담은 후

각 인덱스 마다 Answer = Max(Icache + Dcache)를 했다. 

 

4. 코드

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

//증가하는 수열 캐시
int Icache[1001];
//감소하는 수열 캐시
int Dcache[1001];


void Icount(vector <int> &nums) {
	Icache[0] = 1;
	//전체 캐쉬를 다 채워야 한다
	for (int i = 1; i < nums.size(); i++) {

		//전에 있던 것들을 하나씩 보면서 @나보다 작으면@ 그 인덱스의 Icache+1 값을 내 Icache에 저장
		// && 이때 여러개면 > 가장 큰 값만 저장!!!!!
		int max = 1;
		for (int j = 0; j < i; j++) {
			if ((nums[j] < nums[i]) && (Icache[j] + 1 > max)) {
				max = Icache[j] + 1;
			}
		}
		Icache[i] = max;
		cout << "Increase "<<i << ":" << max << "\n";
	}	
}

//Icount와는 반대로!!
void Dcount(vector <int>& nums) {
	Dcache[nums.size()-1] = 1;
	//전체 캐쉬를 다 채워야 한다
	for (int i = nums.size()-2; i >= 0; i--) {

		//전에 있던 것들을 하나씩 보면서 @나보다 작으면@ 그 인덱스의 Icache+1 값을 내 Icache에 저장
		// && 이때 여러개면 > 가장 큰 값만 저장!!!!!
		int max = 1;
		for (int j = nums.size() - 1; j >i; j--) {
			if ((nums[j] < nums[i]) && (Dcache[j] + 1 > max)) {
				max = Dcache[j] + 1;
			}
		}
		Dcache[i] = max;
		cout << "Decrease " << i << ":" << max << "\n";
	}
}

int Answer[1001];

int solve(vector <int> &nums ) {
	int max = 1;
	for (int i = 0; i < nums.size(); i++) {
		Answer[i] = Icache[i] + Dcache[i] -1;
		if (max < Answer[i]) {
			max = Answer[i];
		}
	}
	return max;
}

int main() {
	//숫자 개수
	int n;
	cin >> n;
	vector <int> nums(n);
	for(int i = 0; i < n; i++) {
		cin >> nums[i];
	}

	Icount(nums);
	Dcount(nums);

	cout << solve(nums);

}

당연한 말이겠지만 중간에 디버깅용으로 찍어놓은 출력문은 빼고 제출해야 된다.

멍청하게도 출력문을 몇번 빼먹고 제출해서 출력문오류가 한 세번났다 ㅋㅋㅋ

 

첫 게시글인데 누군가에게 도움이 되었으면,,!! 이해가 안된다면 댓글 달아주시면 아는 한 설명해드릴게요~

앞으로 꾸준히 써야지

 

p.s. 그나저나 깃에 올려야되는데 귀찮다ㅏ...