백준_가장 긴 증가하는 부분수열_11053

// 알고리즘

1. dp

 

2. 현재 인덱스를 기준으로 이전 인덱스들을 탐색

 -> 만약 이전값이 현재 값보다 크다면 패스

 -> 이전값이 현재 값보다 작다면 dp 테이블을 비교하여 이전값의 dp테이블 +1

 

3. 생성된 dp 테이블에서 가장 큰 값이 가장 긴 증가하는 부분수열임.

 

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

public class 가장긴증가하는부분수열_11053 {
	static int N, arr[], dp[];

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		arr = new int[N];
		dp = new int[N];

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		int max = 0;
		for (int i = 0; i < N; i++) {
			dp[i] = 1;
			for (int j = 0; j < i; j++) {
				if (arr[i] > arr[j] && dp[i] < dp[j] + 1) {
					dp[i] = dp[j] + 1;
				}
			}
			if (max < dp[i])
				max = dp[i];
		}

		System.out.println(max);
	}

}

 

※ 공식과도 같은 문제라 한번 테이블을 그려보면서 이해하고 구현했음. 

2중 for문이기 때문에 시간복잡도는 n*n 임 따라서 n이 10만 이상 주어진다면 해당 방법으로는 풀 수 없음.