[java] 11053번 가장 긴 증가하는 부분 수열

1. 문제 링크 및 문제

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

2. 해결 방법 생각해보자 ...

증가하는 부분 수열 이므로,
2중 반복문을 통해 변수값을 하나씩 늘려가며 계산

백준예시 1을 통한 이해
예시)
6
10 20 10 30 20 50

증가하는 부분 수열의 길이를 구해야함, 배열이 주어진 이상 길이는 1이므로 초기값은 1 -> dp[0] = 1

1. i=1 일 때, arr[1] =20 를 j 값들과 비교
   j = 0 , arr[0]

arr[0]<arr[1] = 10<20 이므로, dp[1] = dp[0]+1

2. i=2 일 때, arr[2] = 10 을 j값들과 비교
j=0, j=1을 비교, arr[0], arr[1]을 비교

arr[i] 즉, 10 보다 큰 값이 없으므로 dp[i] = 1

3. i=3 일 때, arr[3] = 30 을 j값들과 비교
j=0, j=1, j=2== arr[0] arr[1] arr[2]
arr[0] <arr[3] 이므로, dp[3] = dp[0]+1 = 2
10 < 30
arr[1] <arr[3] 이므로, dp[3] = dp[1]+1 = 3
20 < 30
arr[2] <arr[3] 이므로, dp[3] = dp[2] + 1= 2
10< 30
중 최댓값인 3

4. i=4 일 때, arr[4] = 20 을 j값들과 비교
   

5. i=5 일 때, arr[5] = 50 을 j값들과 비교
   j=3일때, dp[5] = dp[3]+1
   

3. 코드

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

public class Main {

    static int N;
    static int[] arr;
    static int[] dp;
    static int MaxResult = 1;

    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());
        }

        dp[0] = 1;

        for(int i=1;i<N;i++){
            dp[i] = 1;
            for(int j=0;j<i;j++){
                if(arr[j]<arr[i]){
                    dp[i] = Math.max(dp[j]+1,dp[i]);
                    MaxResult = Math.max(dp[i], MaxResult);
                }
            }
        }
        System.out.println(MaxResult);
    }

}