[백준][DP] 11053번 가장 긴 증가하는 부분 수열

문제

N개의 원소를 가지는 수열이 주어졌을 때 가장 긴 증가하는 부분 수열의 크기를 구하시오.

문제 출처: 백준 온라인 저지(https://www.acmicpc.net/problem/11053)

풀이

DP를 통해 풀 수 있는 문제입니다. DP문제는 생각이나 구현면에서 다른 알고리즘에 비해 시간이 적게 걸린다는 장점이 있어서 요즘 공부를 하다가 집중이 안될 때 풀고 있는 중입니다! 풀이를 안적어도 될 정도로 간단한 문제들이 많지만 오랜만에 적어보겠습니다. 이 문제에서는 수열이 주어지고 가장 긴 증가하는 부분 수열을 구해야하기 때문에 두조건을 만족하는 경우 큰수가 dp배열에 저장될 수 있도록 했습니다. nums[i], dp[i] 라는 배열을 만들었고 nums에는 입력받은 값이 들어가있습니다. dp[i]의 값은 num[0~i-1] 중에서 num[i] 보다 작은 값이고, 그때의 dp[j]+1 이 가장 큰 값을 고르게 됩니다. 이렇게 되면 i번째가 되었을 때는 이전에 만들어놓은 수열 중 가장 긴 수열에 자신도 포함하여 +1을 해주게 되는 것입니다. 제목도 증가하는 수열인데 모르고 같은 값이 이어질 때도 수열로 만들어주어서 틀렸습니다를 받았었습니다.

코드

https://github.com/kswim/Algorithm/blob/master/DP/11053.cpp