문제는 https://www.acmicpc.net/problem/12015 이것

저번주 금욜에 프갤에 올라왔던건데 어제 자기전에 아이디어 떠올라서 드뎌 풀었다 ㄲㄲ


#include <stdio.h>

#define inf 987654321


int ans;

int cash[1000001];

int dataa[1000001];

int n;


void search(int target, int left, int right)

{

if (left > right)

{

if (target < cash[right+1])

{

cash[right + 1] = target;

if (ans < (right + 1))

{

ans = right + 1;

}

}

return ;

}

int mid = (left + right) / 2;


if (cash[mid] < target)

{

search(target, mid + 1, right );

}

else

{

search(target, left , mid - 1);

}

return ;

}



int main()

{

int save, save2;


scanf("%d", &n);


for (int i = 1; i <= n; i++)

{

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

cash[i] = inf;

}

ans = 0;

for (int i = 1; i <= n; i++)

{

search(dataa[i],1,ans);

}


printf("%d\n", ans);


return 0;

}



지금 체크할 숫자보다 작으면서 가장 큰 카운트를 어떻게 찾을것인가 생각해내는 거였는데 

풀어낸 아이디어 핵심은 바이너리서치로

n카운트보다 큰지 작은지를 판단하기 위해서 필요한 정보는 n카운트에서 가장 작은 데이터 하나임

그 하나만 넣어놓는 배열 만들면 되더라


풀어말하면

cash[1]은 길이1 부분수열중 가장 맨끝수가 작은 끝수

cash[2]는 길이2 부분수열중 가장 맨끝수가 작은 끝수

cash[3]는 길이3 부분수열중 가장 맨끝수가 작은 끝수

이렇게 저장해놓으면

바이너리서치로 현재 수보다 작은수를 찾으면 됨


데이터를 처리할때 symbol을 잘 설정하는것이 상급알고리즘문제의 열쇠인듯