궤도

문제 풀이 대표적인 동적계획법 문제이다. 증가하는 부분 수열을 담은 max_num이란 배열이 있다고 하자. max_num의 상태는 다음과 같다. 10 20 30 현재 max_num의 길이는 3이니 가장 긴 증가하는 부분 수열의 길이도 3이라고 할 수 있겠다. 이때, 15가 들어오는 경우와 50이 들어오는 경우를 살펴보자. 15가 들어오는 경우 가장 오른쪽의 숫자인 30부터 비교를 시작한다. 왜 왼쪽부터가 아니라 오른쪽부터 비교하냐면 우리의 목적은 제일 긴 수열을 찾는 것이고, 가장 큰 수가 오른쪽에 저장됐을 것이다. 새로 들어오는 수가 이 수보다 크다면, 한 번에 수열의 길이를 하나 늘릴 수 있는 것이다. 아무튼 30과 비교하니 1530이란 것을 발견한다. 그렇다면 가장 긴 수열의 길이를 하나 늘릴 수 ..