백준 14003, 가장 긴 증가하는 부분 수열 5

문제

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

풀이

이것도 전 포스트와 마찬가지로 내머리로는 풀 수 없을 것 같아서 컨셉을 보고 했다. 저장할때 저장한 위치를 저장하고 그것을 바탕으로 뒤에서부터 위치 순서대로 출력해서 했다. 뒤에서부터 memo에 저장한 것을 확인해야 하는 것을 주의하자. (그래야 정상 출력됨)

실수

• arr에 넣고 memo에 size를 넣어서 처음에 넣을때는 memo에 저장되어야 하는 값보다 1 추가된 것이 들어가는 문제가 있었다.
• 이것 저것 주먹구구 식으로 해서 디버깅이 없었으면 시간이 오래 걸렸을것 같다. 관련 문제를 풀면서 익숙해지는게 좋을 것 같다.

코드

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>

using namespace std;

vector<int> input(1100000, 0);
vector<int> dp(1100000, 0);
vector<int> arr;
vector<int> memo(1100000, 0);
vector<int> res;

int lowerbound_bs(int s, int e, int target) {

	while (s < e) {

		int mid = (s + e) / 2;

		if (target <= arr[mid])
			e = mid;

		else
			s = mid + 1;

	}

	return s;

}

int main() {

	int n;

	scanf("%d", &n);

	for (int i = 0; i < n; i++) {

		scanf("%d", &input[i]);

	}

	arr.push_back(-1 * 2e9);

	for (int i = 0; i < n; i++) {

		int s = lowerbound_bs(0, arr.size(), input[i]);

		if (s == arr.size()) { // 크면 뒤에

			memo[i] = arr.size();
			arr.push_back(input[i]);

		}

		else if (arr[s] > input[i]) { // 작은걸로 대체

			arr[s] = input[i];
			memo[i] = s;

		}

	}

	printf("%d\n", arr.size() - 1);

	int cnt = arr.size() - 1; // 뒤부터
	int val = -1;

	for(int i = n - 1; cnt != 0; i--) // 처음 만나는 cnt와 같은 것을 출력, 뒤부터 해보니까 2부터 시작함. 왠지는 모름 이거 memo저장할때 넣고 저장해서 새로 저장할때는 + 1 상태였음.
		if (cnt == memo[i] && input[i] != val) { // 마지막 값과 같으면 안됨 (갱신되다가 이런 경우가 생김)

			res.push_back(input[i]);
			val = input[i];
			cnt--;

		}

	for (int i = res.size() - 1; i >= 0; i--)
		printf("%d ", res[i]);

	return 0;

}