[백준/11053/Java/DP] 가장 긴 증가하는 부분 수열 (LIS)

 

문제링크

www.acmicpc.net/problem/11053

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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

 

풀이

이 문제는 가장 긴 증가하는 부분 수열을 구하는 문제입니다.

DP에서 유명한 LIS(Longest Increasing SubSequence) 문제입니다.

증가하는 수열을 구하려면 현재와 이전 값을 비교해서 더 큰 값인 경우 길이를 하나씩 늘릴 수 있습니다.

 

문제에 있는 예제로 어떻게 동작하는지 알아보도록 하겠습니다.

 

초기값

입력으로 주어진 수열은 A 배열에 저장하고 부분수열의 길이를 D 배열에 저장하도록 하겠습니다.

모든 값은 그 자체만으로도 길이가 1인 수열입니다.

따라서, D 배열에 1로 초기화합니다.

 

 

A[2]까지의 부분수열

A[2] 기준으로 가장 긴 증가하는 수열의 길이를 구해보도록 하겠습니다.

A[2]와 A[1]을 비교하면 A[2] > A[1], 20 > 10으로 A[2]가 큽니다.

따라서, A[1]까지의 길이보다 1만큼 더 깁니다.

그러므로 D[1] + 1 = 2 = D[2]가 됩니다.

 

A[3]까지의 부분수열

A[3]은 A[1], A[2] 보다 크지 않습니다.

따라서, 증가하는 수열이 아니므로 D[3]은 그대로 유지합니다.

 

A[4]까지의 부분수열

A[4]은 A[1] ~ A[3]까지의 값과 비교하여 증가하는지 확인합니다.

A[4] > A[1]이므로 D[4] = D[1] + 1 = 2입니다.

A[4] > A[2]이므로 D[4] = D[2] + 1 = 3입니다.

A[4] > A[3]이므로 D[4] = D[3] + 1 = 2입니다.

이 중 가장 큰 값은 3이며, A[4] > A[2]가 되는 경우입니다.

즉, 이 부분수열은 A[1], A[2], A[4] = 10, 20, 30입니다.

 

A[5]까지의 부분수열

A[5]은 A[1] ~ A[4]까지의 값과 비교하여 증가하는지 확인합니다.

A[5] > A[1]이므로 D[5] = D[1] + 1 = 2입니다.

A[5]와 A[2]는 값이 같으므로 증가하는 수열이 아닙니다.

A[5] > A[3]이므로 D[5] = D[3] + 1 = 2입니다.

이 중 가장 큰 값은 2이며, A[5] > A[1] 또는 A[5] > A[3]이 되는 경우입니다.

즉, 이 부분수열은 A[1], A[5] 또는 A[3], A[5]로 2가지 경우가 존재합니다.

 

A[6]까지의 부분수열

A[6]은 A[1] ~ A[4]까지의 값과 비교하여 증가하는지 확인합니다.

A[6] > A[1]이므로 D[6] = D[1] + 1 = 2입니다.

A[6] > A[2]이므로 D[6] = D[2] + 1 = 3입니다.

A[6] > A[3]이므로 D[6] = D[3] + 1 = 2입니다.

A[6] > A[4]이므로 D[6] = D[4] + 1 = 4입니다.

A[6] > A[5]이므로 D[6] = D[5] + 1 = 3입니다.

이 중 가장 큰 값은 4이며, A[6] > A[4]인 경우입니다.

즉, 이 부분수열은 A[1], A[2], A[4], A[6] = 10, 20, 30, 50입니다.

 

A[i] 기준으로 A[0] ~ A[i-1]까지 값을 비교하고, 가장 길이가 긴 경우를 찾아서 그 길이에 1만큼 더 해주면 됩니다.

 

 

소스

A[i] 기준으로 A[0] ~ A[i-1]까지 확인하기 위하여 for문을 하나 더 만들어서 j 변수로 돌립니다.

A[i] > A[j]보다 크면 D[i] = D[j] + 1을 하면 됩니다.

그리고 D배열의 전체 값 중에서 가장 큰 값을 찾으면 답이 됩니다.

 

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

public class Main
{
	static int N;
	static int A[];
	static int D[];
	static private int Answer;

	public static void main(String[] args) throws Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.valueOf(br.readLine());
		A = new int[N];
		D = new int[N];
		
		String input = br.readLine();
		StringTokenizer st = new StringTokenizer(input);
		for (int i = 0; i < N; i++)
		{
			A[i] = Integer.valueOf(st.nextToken());
			D[i] = 1;	// 1로 초기화
		}
		
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < i; j++)
			{
				if (A[i] > A[j] && i > 0 && D[j]+1 > D[i])
				{
					D[i] = D[j] + 1;
				}
			}
		}
		
		// 최대값
		for (int i = 0; i < N; i++)
		{
			Answer = Math.max(Answer, D[i]);
		}
		
		System.out.println(Answer);
		
//		System.out.println(Arrays.toString(D));
	}
}