Baekjoon 11053 가장 긴 증가하는 부분 수열 JAVA

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

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

풀이

1. 최장 증가 부분 수열(LIS, Longest Increasing Subsequence)을 이용하여 해결하는 문제이다.

2. DP문제에 맞게, 이전 결과의 값을 이용하여 현재의 값에 대한 결과를 찾는것이다.

3. 특정 시작 위치로부터 자기 자신이 들어간다면 그 값은 1부터 시작한다.

4. 처음 원소부터 현재의 원소의 값 이전까지 찾으면서 현재의 위치보다 이전의 값이 작고,
    이전 자리의 증가 수열의 값에서 1을 더한 것이 현재 위치의 수열보다 크면

    현재 자리의 값을 이전 위치 수열의 값에 1을 더한 값으로 대체한다.​

	10	20	10	30	20	50
i=0	1
i=1	1	2
i=2	1	2	1
i=3	1	2	1	3
i=4	1	2	1	3	1
i=5	1	2	1	3	1	4

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		int[] arr = new int[n], dp=new int[n];
		int maxlen=0;
		for(int i=0;i<n;i++)
			arr[i]=Integer.parseInt(st.nextToken());
		
		for(int i=0;i<n;i++) {
			dp[i]=1;	// 자기 자신으로 구성하면 길이는 1
			for(int j=0;j<i;j++) {	// 현재 원소부터 i원소 이전까지 비교
				if(arr[j]<arr[i] && dp[j]+1>dp[i])
					dp[i]=dp[j]+1;
			}
		}
		for(int i=0;i<n;i++)
			if(maxlen<dp[i])
				maxlen=dp[i];
		System.out.println(maxlen);
	}
}