백준 11053번 - 가장 긴 증가하는 부분 수열

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

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

 

위의 예제를 바탕으로 풀어보면 다음과 같다.

 

맨 처음 dp[0] 값은 1로 설정하고

 

 

arr[1] 의 값이 arr[0] 보다 크면  

dp[1] 의 값은 dp[0] 에 1을 더한 2로 설정한다.

 

 

arr[2] 의 값이 arr[0] , arr[1] 보다 크지 않기 때문에

dp[2] 의 값은 1로 설정한다.

 

 

arr[3] 의 값이 arr[0], arr[1], arr[2] 보다 크기 때문에

dp[3] 의 값은 dp 값 중 가장 큰 값 2에 1을 더한 3으로 설정한다.

 

 

arr[4] 의 값이 10 보다 크기 때문에

dp[4] 의 값은 10 의 값을 가지고 있는 dp[2] 에 1을 더한 2로 설정한다.

 

 

arr[5] 의 값이 30 보다 크기 때문에

dp[5] 의 값은 30 의 값을 가지고 있는 dp[3] 에 1을 더한 4로 설정한다.

 

 

 

 

 

 

코드

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

public class Main {
    public static void main(String[] args){
       Scanner sc = new Scanner(System.in);
       int N = sc.nextInt();
       int arr[] = new int[N];
       int dp[] = new int[N];
      
       for(int i=0;i<N;i++)
       {
    	   arr[i] = sc.nextInt();
       }
       
       dp[0]=1;
       for(int i=1;i<N;i++)
       {
    	   dp[i]=1;
    	   for(int j=0;j<i;j++)
    	   {
    		   if(arr[i]>arr[j]&&dp[i]<=dp[j])
    		   {
    			   dp[i]=dp[j]+1;
    		   }
    	   }
       }
      
       int max=dp[0];
       for(int i=1;i<N;i++)
       {
    	   if(max<dp[i])
    		   max=dp[i];
       }
       System.out.println(max);
    }
}