백준 3745 - 오름세(C++)

문제 링크입니다 https://www.acmicpc.net/problem/3745

3745번: 오름세

문제 조건

출력 예시

가장 긴 증가하는 부분 수열 o(n log n) 문제였습니다. 저는 lower_bound를 구현했습니다!

 

문제 접근 방법

1. 수열을 입력받은 뒤 오름차순으로 정렬한다.

2. vector에 arr[0]의 값을 입력한 뒤, lower_bound를 실행한다.

3. vector의 크기를 출력한다.

4. 1번~3번을 반복한다.

 

문제 접근 방법 - 2번

void binary_search(int x) {
	int low = 0;
	int high = max_.size() - 1;
	int ret = 1000000;
	while (low <= high) {
		int mid = (high + low) / 2;
		if (max_[mid] >= x) {
			if (ret > mid) ret = mid;
			high = mid - 1;
		}
		else low = mid + 1;
	}
	max_[ret] = x;
}
////////////////////////////////////////////////////////////main 함수속 이진탐색 부분
max_.push_back(arr[0]);
for (int i = 1; i < N; i++) {
	if (max_.back() < arr[i]) max_.push_back(arr[i]);
	else binary_search(arr[i]);
}
///////////////////////////////////////////////////////////

가장 긴 증가하는 부분 수열을 구할 때 필요한 방법은 자신보다 큰 수는 입력받고, 자신보다 작은 수는 비교 후 입력하는  것입니다.

예를 들면 (70, 40, 50, 60, 80, 70, 90, 100)이라는 수열이 있습니다. 이때 lower_bound를 사용하면

1 -> 70

2 -> 40

3 -> 40, 50

4 -> 40, 50, 60

5 -> 40, 50, 60, 80

6 -> 40, 50, 60, 70

7 -> 40, 50, 60, 70, 90

8 -> 40, 50, 60, 70 ,90 ,100 이 됩니다.

따라서 vector의 마지막 수보다 크다면 -> 수를 입력받는다. 작다면 -> 자기보다 큰 수의 위치를 찾은 후 자신과 바꾼다.

 

 

자세한 것은 코드를 참고해주세요!

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>

using namespace std;

int N;
int arr[100001];
vector<int> max_;

void binary_search(int x) {
	int low = 0;
	int high = max_.size() - 1;
	int ret = 1000000;
	while (low <= high) {
		int mid = (high + low) / 2;
		if (max_[mid] >= x) {
			if (ret > mid) ret = mid;
			high = mid - 1;
		}
		else low = mid + 1;
	}
	max_[ret] = x;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	while (1) {
		if (cin >> N) {
			for (int i = 0; i < N; i++) {
				cin >> arr[i];
			}
			max_.clear();
			max_.push_back(arr[0]);
			for (int i = 1; i < N; i++) {
				if (max_.back() < arr[i]) max_.push_back(arr[i]);
				else binary_search(arr[i]);
			}
			cout << max_.size() << "\n";
		}
		else break;
	}
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요!