BOJ ) 11053번 가장 긴 증가하는 부분 수열

https://www.acmicpc.net/problem/11053

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

이번 문제는 다이나믹 프로그래밍을 이용하여 푸는 문제입니다.

 

배열 A를 입력받은 수열이라고 하면

DP[i]는 A[1],A[2],....,A[i] 까지 수열이 있을 때 A[i]를 마지막으로 하는 가장 긴 증가하는 부분수열의 길이라고 둡니다.

우선 처음에는

10을 마지막으로 하는 가장 긴 증가하는 부분수열의 길이는 1입니다.

 

다음의 20은 왼쪽에 있는 수 중 자신보다 작으면서 DP[자신보다 작은 수의 위치] 가 자신의 DP[자신]의 값 보다 크면 그수에 1을 더합니다.

이것을 코드로 만들어 보면 이런식으로 나옵니다.

 

if(A[j]<A[i]&&DP[j]>=DP[i]){

    DP[i]=DP[j]+1;

}

 

다음에 나오는 10은 만족하는 조건이 없으니 자기 자신의 길이인 1이 됩니다.

 

30은 자기보다 왼쪽에 있으면서 작은 수인 20이 있고 20의 길이인 2보다 자신의 길이(1) 이 더 작기 때문에 20의 길이의 자신의 길이를 더한 3이 들어가게 됩니다.

 

이런식으로 채워나가면 다음과같은 표를 만들 수 있게됩니다.

 

 

 

아래는 코드입니다.