[백준 11053번] 가장 긴 증가하는 부분수열

https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

이 문제는 실버 3으로 동적 계획을 사용하는 문제입니다.

---

풀이

이 문제는 LIS라는 유명한 문제입니다. 왜 동적  배열을 이용하는지, 살펴 봅시다

i	0	1	2	3	4	5	6
A	0	10	20	10	30	20	50
DP	0

이런 표가 있다고 해봅시다 보기 쉽게 i=0일때 경우를 추가해봤습니다. LIS 문제를 푸는 키워드는 다음과 같습니다

해당 값이 어떤 증가 부분수열의 마지막보다 큰지를 본다!

 

i	0	1	2	3	4	5	6
A	0	10	20	10	30	20	50
DP	0	1

 i가 1일때 입니다. A[1]은 A[0]보다 큽니다 따라서 부분 증가수열에 포함이 됩니다. 따라서 해당 부분수열의 수는 1입니다.

i	0	1	2	3	4	5	6
A	0	10	20	10	30	20	50
DP	0	1	2

i가 2일때입니다. 마찬가지로 부분수열 dp[1]의 마지막 수인 10보다 a[2]가 크기 때문에 부분증가 수열을 만들수 있습니다. 따라서 dp[2]=dp[1]+1 =2입니다. 

i	0	1	2	3	4	5	6
A	0	10	20	10	30	20	50
DP	0	1	2	1

i=3일때입니다.  a[3]은 dp[2]의 마지막 수인 a[2]보다 작기 때문에 dp[2]의 뒤에는 이을 수 없습니다 하지만 dp[0]보다는 크기 때문에 dp[3]은

dp[0]+1=1입니다

i	0	1	2	3	4	5	6
A	0	10	20	10	30	20	50
DP	0	1	2	1	3

i=4일때 A[4]는 dp[3]의 마지막 수인 A[3]보다 크므로 dp[3]+1이다 생각할수 있습니다 하지만 저희는 가장 긴 증가 부분 수열을 찾는 것이므로 dp[2]의 뒤에다 이을 수 있습니다. 그러므로 dp[4] = dp[2]+1 = 3 입니다.

 

i	0	1	2	3	4	5	6
A	0	10	20	10	30	20	50
DP	0	1	2	1	3	2

i=5일때입니다. A[5]는 dp[4]의 마지막 수인 A[4]보다는 작습니다. 그렇기에 가장 길면서 a[5]보다 작은 dp[3]의 뒤에 붙어 2라는 값을 갖습니다.

i	0	1	2	3	4	5	6
A	0	10	20	10	30	20	50
DP	0	1	2	1	3	2	4

마지막 i=6일때입니다. 마찬가지로 a[6]보다 마지막 수 가 작으면서 가장 많이 증가해있는 수열은 dp[4]의 수열입니다. 따라서 dp[4]+1=4입니다. 따라서 가장 긴 수열은 4입니다.

---

코드

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class longSequence {
	public static void main(String arg[]) throws IOException {
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw= new BufferedWriter(new OutputStreamWriter(System.out));
		int n=Integer.parseInt(br.readLine());
		int []a=new int[n+1];
		int []dp=new int[n+1];
		StringTokenizer st= new StringTokenizer(br.readLine());
		for(int i=1; i<=n;i++) {
			a[i]=Integer.parseInt(st.nextToken());
		}
		dp[0]=0;
		a[0]=0;
		for(int i=1;i<=n;i++) {
			for(int j=i-1; j>=0;j--) {
				if(a[i]>a[j]) { //전값보다 커야한다 해당 값이
					if(dp[i]<dp[j]+1) //만약 해당값이 더 크면 바꾼다.
						dp[i]=dp[j]+1;
					
				}
			}
		}
		Arrays.sort(dp);
		System.out.print(dp[n]);
	}
}