가장 긴 감소하는 부분 수열 c++
-
11722) 가장 긴 감소하는 부분 수열 c++백준코딩일기 2021. 2. 5. 16:04
문제 ) www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net 풀이 ) 11053 문제를 먼저 풀었어서 조금 쉬웠다. 문제에서 dp 배열은 가장 긴 증가하는 부분 수열의 길이를 저장하는 배열로 사용했다. 1. 수열 A의 크기가 최소 1이라고 했으므로 dp[i] = 1 로 세팅하고 시작 2. A배열의 맨처음 수부터 계속해서 비교하기 위해서 j의 범위를 i까지 만으로 지정 3. 현재 비교할 수..