백준 11053 가장 긴 증가하는 부분 수열(Silver2)

정답코드

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

public class LongestIncreaseSeries {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int [] series = new int[N];
		int [] DP = new int[N+1];
		Arrays.fill(DP,1);
		
		String[] in= br.readLine().split(" ");
		
		for(int i = 0; i < N; i++) {
			series[i] = Integer.parseInt(in[i]);
		}
		
		for(int i = 1; i < N; i++) {
			for(int j = 0; j<i; j++) {
				if(series[j]<series[i]&&DP[j]>=DP[i]) {
					DP[i] = DP[j]+1;
				}
			}
		}
		
		int result = 1;
		
		for(int i = 0; i< N; i++) {
			result = Math.max(result,DP[i]);
		}
		
		System.out.println(result);
		
	}

} 

전략

• Input 크기가 1000보다 작기 때문에 N^2으로 해도 가능한 문제

• 배열을 순회하면서 자기보다 왼쪽에 있는 수 중에 자기보다 작으면서 DP값이 큰 경우 해당 DP idx에 있는 값 +1 로 자신의 값에 저장하는 방식으로 진행