SWEA 3307 (1) 썸네일형 리스트형 [SWEA] 최장 증가 부분 수열 👀 문제 설명 문제 로그인해야 문제를 볼 수 있다. ✍🏻풀이 DP를 사용해 각 자리까지의 최장 증가 수열을 저장한다. nums는 입력받은 숫자 배열이고, dp는 각 자리까지의 최장 증가 수열을 저장하는 배열이다. dp[0]은 제일 앞에 있는 값이므로 1로 두고 시작한다. i = 1 부터 N - 1까지 접근해 각 자리의 최장 증가 수열을 구한다. 현재자리의 최장 증가 수열은 나의 앞에서 나보다 작은 애들 중의 최장 증가 수열 + 1이다. 예를 들어, nums가 1, 3, 2, 5, 4일 경우 dp[3]을 구하려면 인덱스 0부터 2까지 돌면서 나보다 작은 애들의 최장 증가 수열의 최댓값을 구한다. nums[0], nums[1], num[2] 모두 5보다 작으므로, 얘들의 dp값을 비교하여 최댓값을 가져온다... 이전 1 다음