[백준 11053] 가장 긴 증가하는 부분

문제

풀이

처음엔 단순하게 지나온 수중 가장 큰 수를 기록하고 해당 수보다 큰 수가 나오면 업데이트 하는 방식을 생각했는데, 어림도 없다.

dynamic Programming인 걸 알기에 많이 나왔던 방식중 하나인 해당 인덱스에서 끝나는 경우 최댓값을 이용하기로 했다.

증가하는 배열(정답이 될 배열)을 따로 생성해서 유지한다.
이 배열의 마지막값보다 새로 읽은 값이 큰 경우 -> 배열에 추가(길이 증가)
같은 경우 -> 그대로
작은 경우
1. 배열에서 새로 읽은 값이 들어갈 자리를 찾아 교체한다.
ex) 배열 10 15 20 23인데 18을 읽었다면 20을 18로 교체하는 것이 이득이다. 만약 18이후에 20 23이 다시 나온다면 총 길이가 5가 될 수 있지만, 교체하지 않는다면 총 길이가 4가 된다.

코드

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
int main(){
	
	freopen("input.txt", "r", stdin);
   	int n, k, l, r, m;
   	cin>>n;
 	vector<int> nums, ans;
	for(int i=0; i<n; i++){
		cin>>k;
		nums.push_back(k);
	}  	
	
	ans.push_back(nums[0]);
	for(int i=1; i<n; i++){
		if(nums[i]>ans.back()) ans.push_back(nums[i]);
		else{
			l=0; r=ans.size()-1;
			while(l<=r){
				m=(l+r)/2;
				if(ans[m]==nums[i]) break;
				else if(ans[m]<nums[i]) l=m+1;
				else r=m-1;
			}
			if(ans[m]<nums[i]) m++; 
			ans[m] = nums[i];
		}
	}
	cout<<ans.size();
	return 0;
}