#LIS 썸네일형 리스트형 15. LIS 알고라파덕 LIS 소스.#include void LIS(); int cnt[510][510]; int main() { int testcase; scanf("%d", &testcase); while(testcase >= 1) { --testcase; LIS(); } return 0; } void LIS() { int num[510]; int N, M, i, j, max = 0; scanf("%d", &N); for(i=1; i 더보기 [알고스팟/ALGOSPOT] 15. LIS 안녕하세요~ 알고라파덕입니다~ 이번 문제는 동적 계획법 관련 문제입니다. 동적 계획법은 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 답을 계산해 내는 방법입니다. LIS 문제 어떤 정수 수열에서 0개 이상의 숫자를 지우면 이 수열의 부분 수열 (subsequence) 를 얻을 수 있다. 예를 들어 10 7 4 9 의 부분 수열에는 7 4 9, 10 4, 10 9 등이 있다. 단, 10 4 7 은 원래 수열의 순서와 다르므로 10 7 4 9 의 부분 수열이 아니다. 어떤 부분 수열이 순증가할 때 이 부분 수열을 증가 부분 수열 (increasing subsequence) 라고 한다. 주어진 수열의 증가 부분 수열 중 가장 긴 것의 길이를 계산하는.. 더보기 이전 1 다음
