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

---

dp 배열을 생성하여 dp[i] 는 Array[i]까지의 원소들로 만들 수 있는 부분 수열 길이의 최댓값을 입력할 것이다.

 

그리고 부분 수열의 길이는 최소 1 값을 가지므로, dp의 모든 원소는 디폴트 1을 가진다는 사실은 알 수 있다.

 

 

dp를 채우는 메커니즘을 알아보자.

 

 

위 그림과 같이, dp 6번째 원소를 채워야 하는 상황이라고 생각해보자.

 

 

 

 

Array의 첫번째 원소 10은 40보다 작으므로, 부분수열의 길이는 10이 가진 dp값 1보다 1이 큰 2로 업데이트 할 수 있다.

 

 

 

 

Array의 두번째 원소 20은 40보다 작으므로, 부분수열의 길이는 20이 가진 dp값 2보다 1이 큰 3으로 업데이트 할 수 있다.

 

 

 

 

 

Array의 세번째 원소 30은 40보다 작으므로, 부분수열의 길이는 30이 가진 dp값 3보다 1이 큰 4으로 업데이트 할 수 있다.

 

 

 

Array의 네번째 원소 23은 40보다 작고, 부분수열의 길이는 23이 가진 dp값 3보다 1이 큰 4으로 업데이트 할 수 있지만, 이미 40이 가진 dp값은 4이므로 변화는 없다.

 

 

 

 

Array의 다섯번째 원소 25은 40보다 작고, 부분수열의 길이는 25이 가진 dp값 4보다 1이 큰 5으로 업데이트 할 수 있다.

 

 

 

 

즉, dp[i]를 채우기 위해서 Array[i] 와 Array[0] 부터 Array[i-1]을 비교하고, 

 

Array[i] > Array[j]인 경우 ( j의 범위는 0 ~ i-1)

 

dp[j] + 1 값이 dp[i]값 보다 큰 경우 dp[j]+1을 dp[i]로 업데이트 하면 되는 메카니즘인 것이다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.valueOf(br.readLine());
		int[] dp = new int[N + 1];
		int[] array = new int[N + 1];
		String[] input = br.readLine().split(" "); // 수열을 split을 이용하여 공백을 기준으로 나눈 String 배열로 입력 받는다.
		
		
		for (int i = 1; i <= N; i++) {
			array[i] = Integer.valueOf(input[i - 1]); //입력받은 수열이 String이기 때문에, int로 바꾼 후 array 배열을 채운다.
			dp[i] = 1; //어떤 수가 오든 부분수열 길이의 최솟값은 1이므로 1을 다 입력해준다.
		}

		for (int i = 1; i <= N; i++) {
			for (int j = 1; j < i; j++) {
				if (array[i] > array[j] && dp[j] + 1 > dp[i]) { 
                //1 ~ i-1 번째 원소들 중 i보다 작은 경우 그리고 현재 dp[i] 보다 dp[j]+1이 큰 경우 업데이트
					dp[i] = dp[j] + 1; 
                    
				}

			}
		}
		Arrays.sort(dp); //dp를 오름차순으로 정렬해줌
		System.out.println(dp[N]); // 제일 뒤에있는 값이 최댓값일 것
	}
}