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

예제 입력 1 복사

6
10 20 10 30 20 50

예제 출력 1 복사

4

https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

---

문제 풀이

  해당 문제는 DP 문제로 진행하면서 이전의 DP 중 가장 큰 값에 더해 나가며 진행하는 문제이다. 해당 문제는 DP문제로 분류되어 있지만 이분 탐색으로 푸는 문제이지만, 분류가 DP이므로 DP로 풀었다. 그렇기에 DP 문제인데도 불구하고 O(N*N)의 시간 복잡도를 가지고 있다. 

 

위 예제의 수열은 {10, 20, 10, 30, 20, 50} 이다. 이를 seq라고 하고, dp[] 배열에 메모이제이션을 한다.

 

 먼저 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[0] = {10} : 길이 1

dp[1] = {10, 20} : 길이 2

dp[2] = {10} : 길이 1

dp[3] = {10, 20, 30} : 길이 3

dp[4] = {10, 20} : 길이 2

dp[5] = {10, 20, 30, 50} : 길이 4

 

---

풀이 코드

bottom-up (본인 풀이)

import java.util.*;
import java.io.*;
public class Main {
	public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	
	
	public static void main(String[] args) throws IOException{
		int T = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int[] board = new int[T+1];
		int[] dp = new int[T+1];
		int max = 0;
		
		int count = 1;
		while(T-- > 0) {
			board[count] = Integer.parseInt(st.nextToken());
			count++;
		}count--;
		
		
		for(int i = 1 ; i <= count; i++) {
			dp[i] = 1;
			for(int j = 1; j <= i; j++) {
				if(board[j] < board[i] && dp[i] < dp[j] + 1) {
					dp[i] = dp[j] + 1;
				}
			}
			if(max < dp[i])max= dp[i];
		}
		System.out.println(max);
	}

}

 

(참고) top-down (출처 : https://st-lab.tistory.com/137)

static int LIS(int N) {
		
	// 만약 탐색하지 않던 위치의 경우 
	if(dp[N] == null) {
		dp[N] = 1;	// 1로 초기화 
			
		// N 이전의 노드들을 탐색 
		for(int i = N - 1; i >= 0; i--) {
			// 이전의 노드 중 seq[N]의 값보다 작은 걸 발견했을 경우
			if(seq[i] < seq[N]) {
				dp[N] = Math.max(dp[N], LIS(i) + 1);
			}
		}
	}
	return dp[N];
}