우선 증가하는 부분수열 문제를 dp로 풀수 있다면 이 문제또한 쉽게 풀수 있을것이다. 애초에 앞의 상자보다 값이 작으면 뒷 상자에 넣을수 있다는 조건이, LIS 문제의 정의와 같다. 다만 주의해야 할 점은, if 조건문에서 단순히 이전값이 현제 인덱스의 값보다 작을시, 이전 dp값에 +1한 것을 현재dp값에 더해주는것을 가능하게하는 조건으로 작용하는 것이 아니라,(아래의 코드에서 dp[i]=dp[j]+1 부분) 이전 dp의 값+1 한 것이 현재 dp의 값보다 커야한다라는 조건도 있어야 된다는 것이다. 나도 처음에 이 조건이 왜 필요한지 생각하느라 애를 참 많이 썼는데, 간단히 설명하자면 이전 값이 현재의 값보다 더 작다는 조건에 만족하는 중복된(같은수)를 카운트하는것을 방지하기 위한 장치이다. 예를 들면..