[백준] 11053: 가장 긴 증가하는 부분 수열

문제

문제 풀이

작은 문제들을 풀어서 결합하는 방식으로 반복문을 사용하는 bottom-up 방식과 재귀 방식을 사용하는 top-down방식 두가지로 나눠서 확인하였다.

- bottom-up 방식

우선 i번째 dp값을 알기 위해서 0부터 i-1번째까지의 원소를 비교하였다.

1. i번째 원소보다 j번째 원소가 더 작아야 한다.
2. i번째 dp값보다 j번째 원소를 선택하고, i번째 원소를 선택한 dp값이 더 커야 한다.

다음과 같은 조건을 만족하게 되면, dp[i]의 값은 dp[j]+1의 값을 가지게 된다.
(여기서 dp[j]에 1을 더한 이유는 i번째 원소를 선택했을 경우이다.)

다음 알고리즘을 통해서 채워진 dp값에 대하여 가장 큰 값을 구하면 된다.

- top-down 방식

N이전의 노드를 탐색하면서 재귀를 통해서 최대값을 구하였다.

1. n번째 원소보다 작아야 한다.
2. 현재 dp값과 n번쨰 원소보다 작은 인덱스의 재귀함수 값에 1을 더한 값중 최대값이 dp[N]이 된다.

코드

import java.util.Scanner;


public class Main {

    static int N ;
    static int[] A, dp;

    public static void main(String[] args){

        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();

        A = new int[N];
        dp = new int[N];


        //수열 A의 값 채우기
        for(int i = 0 ; i < N ; i++){
            A[i] = sc.nextInt();
        }


        //dp
        for(int i = 0 ; i < N ; i++){
            dp[i] = 1; //초기화

            for(int j = 0 ; j < i ; j++){
                //j번째 원소가 i보다 작으면서 i번째 dp가 j번째  dp+1 값보다 작은 경우
                if(A[j] < A[i] && dp[i] < dp[j]+1){
                    dp[i] = dp[j] +1;
                }
            }
        }

        int max = -1;
        for(int i = 0 ; i < N ; i++){
            max = dp[i] > max? dp[i] : max;
        }

        System.out.println(max);


    }

}

---

하나를 알면 열을 알고 싶은 사람이 되고 싶지만
하나를 제대로 아는것만 해도 대단한 것 같다..ㅎ