🙇‍♀️[Gold II] 가장 긴 증가하는 부분 수열 3 - 12738

문제 링크

성능 요약

메모리: 12200 KB, 시간: 188 ms

분류

이분 탐색, 가장 긴 증가하는 부분 수열: O(n log n)

제출 일자

2024년 2월 25일 17:51:12

문제 설명

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

🚀풀이

가장 긴 증가하는 부분 수열 2의 정답에서 약간의 꼼수만 추가해서 풀었다.

2와 3의 차이점은 입력값의 음수의 여부인데, 음수의 경우를 계산하지 않기위해서 그냥 처음부터 가중치를 넣어서 계산해서 풀었다.

루키스 강의에서 DP로 풀었던 기억이 있는데 이분탐색의 방법으로 하는게 정석인듯?
사실 잘 모른다.

🚀전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

int arr[1000001];
vector<int> seq;
int N, weight = 1000000000;

void bs(int num)
{
	int low = 0, high = seq.size() - 1, mid;
	int ret = 100000007; // 왜 이런 숫자로 잡는거지?
	while (low <= high)
	{
		mid = (low + high) / 2;
		int here = seq[mid];
		if (here >= num)
		{
			if (ret > mid)
				ret = mid;
			high = mid - 1;
		}
		else
			low = mid + 1;
	}

	seq[ret] = num;
}

void findLis()
{
	seq.push_back(arr[0]);
	for (int i = 1; i < N; ++i)
	{
		if (seq.back() < arr[i])
			seq.push_back(arr[i]);
		else
			bs(arr[i]);
	}
}

void solve()
{
	cin >> N;
	int temp;
	for (int i = 0; i < N; ++i)
	{
		cin >> temp;

		arr[i] = temp + weight;
	}

	findLis();

	cout << seq.size();
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	freopen("input.txt", "rt", stdin);

	solve();
	
	return 0;
}

참고