이 문제는 동적 계획법(다이나믹 프로그래밍)으로 접근을 해야 합니다.

그래서 2중 for문을 돌리면서 dy배열에 대한 조건을 확인해야 합니다. 잘 이해가 안돼실텐데, 아래 소스를 보면 좋을까요? (뭐, dy배열을 하나 잡아야 하는데, 이름은 반드시 dy가 아니여도 됩니다.

아래 소스의 15번째 줄의 조건문을 이해하는 것이 중요하다고 생각합니다.

일단 O(N^2) 풀이는, a를 위에서처럼 입력  배열이라고 정의하고 dp[i]를 1~i의 수들로 이루어진 최장 길이 증가 수열이라고 정의해서,

dp[i]=max_{(1<=j<=n), a[j]<a[i]}(dp[j]+1) 로 정의하므로서 O(N^2)로 해결해내는 것입니다.

여기서 O(NlogN)풀이는  dp[i]=max_{(1<=j<=n), a[j]<a[i]}(dp[j]+1)를 어떻게 하면 빨리 구할 수 있을까를 생각하시면 될 겁니다..일단 O(N^2)로 이 문제를 Success한 후!

이런 문제는 대부분 위에서처럼 greedy하게 어떻어떻게 하면 답이 나온다!, 즉 답을 이런 경우에는 이렇게, 저런 경우에는 저렇게 처리해서는 안되는 문제들 중 하나입니다.

그렇게 greedy로 처리하는 문제는 https://www.acmicpc.net/proble...이 있죠...

비슷하게 greedy인 것 같은데 dynamic인 문제는  못찾겠지만, 예를 들면

동전이 1, 3, 5가 있는데 9원을 만드는데 드는 최소 동전 개수는 3이죠...5+1+1+1+1=9가 아니조

이런 비슷한 류이기에, 일단 저 문제는 dp 배열을 생각하시고, 정의를 세워서 프로그램을 구현하셔야 할 겁니당

eric00513  , atomzeno 님 감사합니다. 손으로 하나하나 적으면서 보니까 이해되네요!!! 

감사합니다!!!  ~^_^~