11053번: 가장 긴 증가하는 부분 수열 Hint

이 문제는 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배열에서 가장 큰 값을 출력해야 한다.