[백준/java]-11053 가장 긴 증가하는 부분 수열

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

 

 

bottomup방식으로 풀었다.

구하고자 하는 것은 증가하는 부분수열의 길이중 가장 긴 길이이므로

 

배열에 수를 일단 입력받고

dp배열을 하나 더 만들어 해당 인덱스마다 인덱스까지의 최장증가부분수열의 길이를 넣어주었다.

넣어줄 때 중요한 규칙은

오름차순이어야하니 

현재인덱스가 담고 있는 수보다 작은 수여야하고, 

작은 수들마다 각각의 dp값을 갖고 있으니 그 중에서 가장 긴 값에 +1을 해준값을 현재 인덱스에 넣어주면 된다.

 

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

public class Main {
    static int dp[];
    static int arr[];






    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws Exception{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

        int 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[i]=1;
        }
        int max=1;
       for(int i=0;i<N;i++){


           for(int j=0;j<i;j++){

               if(arr[j]<arr[i] ){

                   dp[i]=Math.max(dp[i],dp[j]+1);  //i번째인덱스에서 i보다 작은 인덱스중 작은 숫자가 있다면 그값의 dp와 비교해서 갱신
               }                                   //만약 현재위치의 수보다 작은 숫자가 두개있을때 두값의 dp값중 더 큰 것을 골라야하기때문에

           }
           max=Math.max(dp[i],max);   //구해진 dp 값중 최대 구하기 (최장 증가 부분수열)

       }





        bw.write(String.valueOf(max));
        bw.flush();
        bw.close();
        br.close();




    }
 }

 

 

topdown방식으로도 풀 수 있는데,

탐색하려는 인덱스에서 값보다 이전인덱스의 값이 더 작다면 재귀적으로 호출해가면서 찾아가는 형식이다.

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

public class Main {
    static int dp[];
    static int arr[];






    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws Exception{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

        int 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());  // 수 입력받아서 배열에 저장

        }
        for(int i=0;i<N;i++){
            topdown(i);
        }

        int max=0;
        for(int i=0;i<N;i++){
            if(dp[i]>max){
                max=dp[i];
            }
        }





        bw.write(String.valueOf(max));
        bw.flush();
        bw.close();
        br.close();




    }

    static int topdown(int n){
        if(dp[n]==0){
            dp[n]=1;

            for(int i=n-1;i>=0;i--){
                if(arr[i]<arr[n]){
                    dp[n]=Math.max(dp[n],topdown(i)+1);  //구하려는위치보다 작은값이 있다면 다시 탐색
                }
            }



        }



        return dp[n];
    }















}