[Java] BOJ11053_가장 긴 증가하는 부분 수열

www.acmicpc.net/problem/11053

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

---

문제 제목 그대로 최장 증가 부분 수열 문제이다.

N의 범위가 1000으로 작기 때문에 단순 이중 포문으로도 구현 가능하다.

DP[i]는 i번째 수를 마지막 원소로 가지는 수열의 길이를 의미한다.

 

i번째 이전의 수들을 j번째 수라고 하면 i번째 수가 j번째 수보다 크고 현재 수열의 길이가 dp[j]+1보다 작다면 dp[i]를 업데이트 시켜준다. dp[j]+1의 의미는 j번째 까지의 수열의 길이에 i번째 수가 포함된 길이이다.

 

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

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] arr = new int[N];
		int[] dp = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		int res = Integer.MIN_VALUE;
		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;
				}
			}
			res = Math.max(res, dp[i]);
		}
		System.out.println(res);
	}
}

 

[참고]

N의 범위가 커서 이중 반복문으로 구현이 안되는 문제이다. 풀어보면 좋다.

jihunworld.tistory.com/17

[Java] BOJ12015_가장 긴 증가하는 부분 수열 2