동적계획법테크닉
-
알고리즘 문제 해결 전략 - 9.7) k번째 최대 증가 부분 수열알고리즘 2021. 1. 4. 11:29
알고리즘 문제 해결 전략 책의 k번째 최대 증가 부분 수열. (동적계획법_테크닉) 기존에 풀었던 LIS문제와 달리 k번째 최대 길이 수열을 출력하는 문제였다. #include #include #include #include #include #include using namespace std; const int MAX = 2000000000 + 1;//k번째보다 1개 더 큰수 int n; int cacheLen[501], cacheCnt[501], S[500]; int lis(int start) {//S[start]에서 시작하는 증가 부분 수열 중 최대 길이를 반환 int& ret = cacheLen[start + 1];//메모이제이션 if (ret != -1) return ret; ret = 1; //항..