[Softeer 🌟🌟🌟] 징검다리(C++)

※주의※

저의 풀이가 정답은 아닙니다.

다른 코드가 더 효율적이거나 좋을 수 있습니다.

언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

 

 

[문제 풀이 사이트]

 

 

Softeer

 

 

[문제 설명]

 

 

남북으로 흐르는 개울에 동서로 징검다리가 놓여져 있다.
이 징검다리의 돌은 들쑥날쑥하여 높이가 모두 다르다. 철수는 개울의 서쪽에서 동쪽으로 높이가 점점 높은 돌을 밟으면서 개울을 지나가려고 한다.
돌의 높이가 서쪽의 돌부터 동쪽방향으로 주어졌을 때 철수가 밟을 수 있는 돌의 최대 개수는?

 

 

[제약 조건]

 

 

1 ≤ N ≤ 3×103 인 정수

1 ≤ Ai ≤ 108 인 정수

 

 

[입력형식]

 

 

첫 번째 줄에 돌의 개수 N이 주어진다.

두 번째 줄에 돌의 높이 Ai (1 ≤ i ≤ N)가 서쪽부터 동쪽으로 차례로 주어진다.

 

 

[출력 형식]

 

 

첫 번째 줄에 철수가 밟을 수 있는 돌의 최대 개수를 출력하라.

 

 

[입출력 예제]

 

 

입력	출력
5 3 2 1 4 5	3

 

 

[문제 풀이]

 

 

최장 증가 부분 수열 문제이다.

O(nlogn) 방식을 사용하여 풀었다.

 

[Algorithm] 최장 증가 부분 수열(LIS)

 

 

[최종 코드]

 

 

[GitHub]

 

 

GitHub - SmallPeanutPark/Softeer: Softeer HYUNDAI

 

 

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

using namespace std;

vector<int> LIS;

int main(int argc, char** argv)
{
	int stonecount; cin >> stonecount;
	for(int i = 0; i < stonecount; ++i) {
		int n; cin >> n;
		if(LIS.empty()) {
			LIS.emplace_back(n);
		} else {
			if(LIS.back() < n) {
				LIS.emplace_back(n);
			} else {
				auto location = lower_bound(LIS.begin(), LIS.end(), n);
				*location = n;
			}
		}
	}
	cout << LIS.size();
	return 0;
}