이 문제는 DP로 해결할 수 있는 문제이다. 쉬운 문제였지만 나는 고민을 많이 했고, 몇 번 틀렸다. 나와 같은 분을 위해 이 글을 남긴다. 1. 나보다 작은놈 여기여기 붙어라! DP 배열을 arr, 입력받은 배열을 in이라고 하자. arr[i]는 in[0 ~ i]을 고려할 때, 마지막 숫자가 in[i]인 가장 긴 (증가하는) 부분 수열의 길이를 의미하도록 구현한다. 백준의 예제 입력을 예로 들면: Input: 6 10 20 10 30 20 50 DP Array: [1, 2, 1, 3, 2, 4] 2. 마지막 원소가 정답은 아니다. 1과 같이 구현하면 DP배열은 입력 배열 i번째 숫자가 마지막인, 가장 긴 부분 수열의 길이를 담게 된다. 그러므로 DP배열에서 가장 큰 값을 출력해야 한다.