[SWEA] 3307. 최장 증가 부분 수열

문제

주어진 두 수열의 최장 증가 부분 수열(Longest Increasing Subsequence)의 길이를 계산하는 프로그램을 작성하시오.

수열 { A1, A2, ... , AN }의 최장 증가 부분 수열 B는 다음과 같이 정의된다.

{ B1, B2, ... , BK }에서 0≤K≤N, B1 ≤ B2 ≤ ... ≤ BK이고,

AB1 ≤ AB2 ≤ ... ≤ ABK인 최대 K로 구성된 수열이다.

예를 들어, 수열이 { 1, 3, 2, 5, 4, 7 } 이라면, 최장 부분 증가 수열의 길이는 4가 된다.

 

풀이방법

동적 계획법(DP, Dynamic Programming)을 이용해서 해결할 수 있다.

 

입력된 수열의 길이와 같은 배열을 하나 선언하고 배열에 i번째 원소에는 

 

수열의 i번째 원소까지의 최장길이가 저장된다.

 

입력된 수열을 a[n]이라 하고 최장길이를 저장하고 있는 배열을 dp[n]이라고 하자

 

a = {1, 3, 2, 5, 4, 7}일 때, 첫 번째 원소의 최장길이는 1이된다.

dp ={1, , , , , ,} 

 

계속해서 인덱스를 늘려가며 최장길이를 탐색한다.

 

a = {1, 3, 2, 5, 4, 7}

dp ={1, 2, , , , ,} 

 

a = {1, 3, 2, 5, 4, 7}

dp ={1, 2, 2, , , ,} 

 

동적계회법을 사용하는 이유는

 

i번째 원소까지의 최장수열은 아무리 짧아도 i-1번째 원소까지의 최장수열 길이와 같고

 

길어도 i-1번째 최장수열 길이의 + 1이기 때문이다.

 

따라서 i번째 원소까지의 최장 수열의 길이는 i-1번째 최장수열의 길이와 같거나 1을 더한 값이 된다.

 

소스코드

package samsung;

import java.util.*;

public class s_3307 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int tc = sc.nextInt();
		
		for(int t = 1; t <= tc; t++) {
			int n = sc.nextInt();
			int[] a = new int[n];
			int[] dp = new int[n];
			int max = 0;
			dp[0] = 1;
			
			for(int i = 0; i < n; i++) {
				a[i] = sc.nextInt();
			}
			
			for(int i = 1; i < n; i++) {
				dp[i] = 1;
				for(int j = 0; j < i; j++) {
					if(a[j] < a[i] && dp[j] + 1 > dp[i]) {
						dp[i] = dp[j] + 1;
					}
				}
				max = Math.max(dp[i], max);
			}
			System.out.println("#" + t + " " + max);
		}
	}
}