백준 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

코드

import java.util.*;
import java.io.*;

public class Main {
	static int[] sequence;
	static Integer[] dp;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		sequence = new int[N];
		dp = new Integer[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		for(int i=0; i<N; i++)
			sequence[i] = Integer.parseInt(st.nextToken());
		
		for(int i=0; i<N; i++)
			Func(i);
		
		int max = dp[0];
		
		for(int i=1; i<N; i++)
			max = Math.max(max, dp[i]);
		
		System.out.println(max);
	}
	
	static int Func(int N) {
		if(dp[N] == null) {
			dp[N] = 1;
			
			for(int i=N-1; i>=0; i--) {
				if(sequence[i] < sequence[N])
					dp[N] = Math.max(dp[N], Func(i)+1);
			}
		}
		
		return dp[N];
	}
}

풀이

처음에 문제를 읽었을 때는 이해하기 어려웠다. 예시를 보면서 이해해보는게 좋다.
sequence = {10, 20, 10, 30, 20, 50}일때,

먼저 seq[0] = 10에 대한 수열을 찾아보면 seq[0]보다 이전 값은 없으므로 10 자체 하나밖에 존재하지 않으므로 dp[0] = 1 이 된다. 그 다음 seq[1] = 20에 대한 수열을 찾아보면 seq[0] = 10으로 20보다 작기 때문에 {10, 20} 이라는 부분수열이 되고, 길이는 2로 dp[1] = 2가 되는 것이다. seq[2] = 10의 경우 이전 값들 중 작은게 없으므로 {10} 하나만 되므로 dp[2] = 1이 된다.

이러한 방식으로 dp를 구하면,
dp = {1, 2, 1, 3, 2, 4} 가 된다.

이를 재귀를 활용하는 Top-Down 접근 방식으로 해결했다.