DynamicProgramming 백준 알고리즘 자바 11053 ‘가장 긴 증가하는 부분 수열’ 문제풀이

Problem

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

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

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

Solution

dp[i]는 i번째 숫자를 포함한 증가 수열의 숫자 개수를 의미한다.
0부터 i-1번째까지 숫자 중 i번째 숫자보다 작은 수들의 수열의 개수를 비교한다. 그들 중 가장 큰 값 + 1이 dp[i]의 값이다.

• ex) 1 4 5 2 3 4 5 가 있을 때, 네번째 수 2보다 작은 수는 1,4,5 중에 1 하나이다. 1의 수열의 숫자 개수는 1이다. 따라서 dp[4]는 2가 된다. 다섯번째 수 3보다 작은 수는 1,4,5,2 중 1과 2이며 dp[1]은 1, dp[4]는 2이므로 가장큰 수 2에 1을 더한 수 3이 dp[5]가 된다. 마지막 수 5의 경우 작은 수는 1,4,2,3,4가 되는데, 가장 긴 부분 수열이 되려면 1,2,3,4,5가 되어야 한다. 문제는 두번째 수 4인데, dp[2]의 수열은 1,4이므로 2가 된다. dp[4]도 1,2가 되므로 2가 되는데 dp[5]는 1,2,3이므로 3…따라서 dp[7]은 마지막 숫자 4가 가리키는 dp[6]=4에서 1을 더한 수 5가 된다.

Code

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int max, answer = 1, n = scan.nextInt();
		int[] num = new int[n+1];		

		for(int i = 1; i <= n; i++) num[i] = scan.nextInt();
		int[] dp = new int[n+1]; dp[1] = 1;
		
		
		for(int i = 2; i <= n; i++) {
			max = 0;
			for(int j = 1; j < i; j++) {
				if(num[j] < num[i] && max < dp[j]) max= dp[j];
			}
			dp[i] = max + 1;
			answer = Math.max(answer, dp[i]);
		}
		System.out.print(answer);
	}
}