[BOJ] 11053. 가장 긴 증가하는 부분 수열

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

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

---

접근 방법

일반적인 DP 문제이다. DP 연습을 위해 풀었었다.

 

소스 코드

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

public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.valueOf(br.readLine());
        int[] arr = new int[N];
        int[] dp = new int[N];
        Arrays.fill(dp, 1);
        
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i=0; i<N; i++)
            arr[i] = Integer.valueOf(st.nextToken());
        
        for(int i=1; i<N; i++)
            for(int j=1; j<=i; j++)
                if(arr[i-j] < arr[i])
                    dp[i] = Math.max(dp[i], dp[i-j]+1);
        
        int m = 1;
        for(int i=0; i<N; i++)
            if(m < dp[i])
                m = dp[i];
        
        System.out.println(m);
    }
}