가장 긴 감소하는 부분수열1 [Swift][DP] 백준 11722번 (가장 긴 감소하는 부분 수열) 요구능력 : DP에대한 이해 코드설명 : 가장 긴 증가하는 부분수열 문제와 부등호만 틀리다. 가장 긴 감소하는 부분수열을 구하는 문제이다. 예제를 보자. 10 30 10 20 20 10 여기서 i인덱스(3)가 20을 가리킨다고 가정하고 설명하면 arr[0]부터 arr[2]까지의 수 중에서 arr[3]보다 큰 수가 있으면 dp[i]를 갱신해준다. 감소하는 부분수열이라서 앞에 나보다 큰 수가 있으면 dp[i]를 갱신해주는것이다. 그럼 dp[i]는 dp[0]부터 dp[2]까지 중에 조건을 만족하는 dp[]를 갖고 +1을 해줄것이다. dp[1]도만족하고 dp[2]도 만족하는 경우가 있으면 max()로 그 중 큰 값을 가져온다. 이유는 그 중 큰값은 이전에 더 많은 감소하는 부분수열을 갖고있을 것이기 때문이다. .. 2021. 11. 10. 이전 1 다음