(JAVA) 백준 11055번 : 가장 큰 증가 부분 수열 --- [LIS, DP]

www.acmicpc.net/problem/11055

11055번: 가장 큰 증가 부분 수열

 

안녕하세요.

 

이 문제는 LIS 알고리즘 응용 문제로, 여러 가능한 부분 수열 중 내부합이 가장 큰 경우의 내부합을 찾는 문제입니다.

 

 

즉, 부분 수열의 값을 다 더했을 경우의 최댓값을 구하면 됩니다.

 

 

여기서는 2중 for문을 사용해서 해결했는데요.

 

좀 더 시간을 줄이기 위해, 하나하나 입력 받을 때 마다 배열에 저장하고, 부분 순열을 만들어나갔습니다.

 

이 때, DP를 사용했는데요.

 

 

  ->  DP[i] = 0 ~ i index 까지의 수 중 만들 수 있는 부분 순열의 내부합 최댓값.

 

구하는 방법

  ->  j = i - 1 ~ 0 일 때, Array[i] > Array[j] 이고, DP[i] < DP[j] + Array[i] 일 경우 DP[i] = DP[j] + Array[i] 로 갱신.

 

 

예를 들어, 

 

10 1 100 2 50 60 3 5 6 7 8

 

가 있을 때,

 

DP[0] = 10

DP[1] = 1

DP[2] = 10 + 100 = 110

DP[3] = 1 + 2 = 3

DP[4] = 1 + 2 + 50 = 53

 

이렇게 쭉 이어지고, 전체 DP 값 중 최댓값을 찾아서 출력하면 문제를 해결할 수 있습니다.

 

 

 

이상입니다.

 

감사합니다!

 

 

 

 

소스코드

---