백준 12738번, 14003번 _ 가장 긴 증가하는 부분 수열 3, 5

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

12738번: 가장 긴 증가하는 부분 수열 3

 풀이방법

 이 문제는 간단하다. 일단 최장 수열을 저장할 vector를 하나 만들었다. (arr이라고 약칭하겠다.)

 그리고 두가지 조건을 통해서 arr을 채워가면 된다.

 

 1. 만약 입력받은 숫자가 arr의 끝에 있는 수보다 크면, arr에 추가

 

 2. 입력받은 숫자가 arr의 끝에 있는 수보다 작다면, arr의 값들 중에서 같거나 가장 차이가 적게나는 큰숫자를 찾아 바꿔서 넣어준다. (c++의 lower_bound 함수를 쓰면 쉽게 찾을수 있다.)

 

 arr의 사이즈가 답이 된다.

 

 주의할 점은 주어지는 수열의 값의 범위가 -10^9 ~ 10^9인점을 유의해서 풀면 될것같다.

---

코드

#include <iostream>
#include <algorithm>
#include <vector>

#define MINF -1000000001

using namespace std;

vector<long long> arr = {MINF};
int N;

int main()
{
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		int tmp;
		cin >> tmp;

		//1.만약 arr의 끝보다 크다면 넣기
		if (arr[arr.size() - 1] < tmp)
			arr.push_back(tmp);
		
		//2. 아니라면 arr lower bound해서 거기다가 바꿔넣기
		else
		{
			int pos = lower_bound(begin(arr), end(arr), tmp) - begin(arr);
			arr[pos] = tmp;
		}
	}

	cout << arr.size() - 1 << endl;
	return 0;
}

---

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

14003번: 가장 긴 증가하는 부분 수열 5

 풀이방법

 이 문제는 위의 문제에서 경로를 역으로 추적해주는 기능을 추가로 구현해야 하는 문제이다.

 그래서 추가로 입력받는 수열을 저장하는 arr, 역추적할수 있게 전 순서의 idx를 저장하는 beforeIdx, 마지막으로 최장수열의 마지막 값의 idx를 쓰기위해서 vxIdx 배열을 추가로 만들었다. 

 

 푸는 방식은 사실 위에서 역추적을 위한 위의 값들을 저장하고 역추적하기만 하면된다. 코드에 주석을 자세하게 써놓았다.

---

 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>

#define MAXN 1000000
#define MINF -1000000001

using namespace std;

long long arr[MAXN + 1];
int beforeIdx[MAXN + 1];
vector<long long> vx = {MINF};
int vxIdx[MAXN+1];
int N;

//역추적값을 저장하기 위한 stack
stack<int> path;

//역추적
void BackTrace(int n)
{
	if (n == 0)
		return;

	path.push(arr[n]);
	BackTrace(beforeIdx[n]);
}

int main()
{
	cin >> N;
	for (int i = 1; i <= N; i++)
	{
		int tmp;
		cin >> tmp;

		arr[i] = tmp;

		//1.만약 vx의 끝보다 크다면 넣기
		if (vx[vx.size() - 1] < tmp)
		{
			vx.push_back(tmp);
			vxIdx[vx.size() - 1] = i;

			//이전 경로 넣어주기
			beforeIdx[i] = vxIdx[vx.size() - 2];
		}
		//2. 아니라면 vx lower bound해서 거기다가 바꿔넣기
		else
		{
			int pos = lower_bound(begin(vx), end(vx), tmp) - begin(vx);
			vx[pos] = tmp;
			vxIdx[pos] = i;

			//이전 경로 넣어주기
			beforeIdx[i] = vxIdx[pos - 1];
		}
	}

	cout << vx.size() - 1 << endl;

	// 마지막 vx의  idx를 기준으로 역추적 ㄱㄱ
	BackTrace(vxIdx[vx.size() - 1]);

	while (!path.empty())
	{
		cout << path.top() << ' ';
		path.pop();
	}

	return 0;
}

---

 최근 다른 일로 정말 바빠서, 정말 오랜만에 푸는 문제풀이었다. 감각이 많이 떨어졌는지 푸는데 조금 애먹었다ㅋㅋㅋ