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

문제 해석

• 수열의 크기 N을 입력받고, N개 만큼 수열을 이루는 숫자를 입력받는다.
• 증가하는 데 가장 길게 증가하는 수열의 길이를 구하기 위해서 각각의 숫자가 어디에 위치해 있는지 알 필요가 있다. (아래와 같이)
  
• 즉, 각의 위치가 길이가 된다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main {

    static int[] arr;
    static Integer[] dp;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        arr = new int[N];
        dp = new Integer[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++) {
            solution(i);
        }

        int max = dp[0]; //최댓값 변수 (초기값 dp[0] 값)

        // 최댓값 찾는 코드
        for(int i = 1; i < N; i++) {
            max = Math.max(max, dp[i]);
        }

        System.out.println(max);
        br.close();
    }


    static int solution(int depth) {

        // 조회하지 않는 것일 경우 
        if(dp[depth] == null) {
            dp[depth] = 1;	// 1로 초기화

            // 현재 위치보다 작은 값들을 찾고 카운트해서 넣는 방식
            for(int i = depth - 1; i >= 0; i--) {
                if(arr[i] < arr[depth]) {
                    dp[depth] = Math.max(dp[depth], solution(i) + 1);
                }
            }
        }
        return dp[depth];
    }
}

		예시로 코드가 실행된다고 하면, 아래와 같이 수행된다.
		A = {10, 20, 10, 30, 20, 50}

        solution(0)
        dp[0] = 1
        i = -1 (i >= 0) false
        => dp[0] = 1

        solution(1)
        dp[1] = 1
        i = 0 (i >= 0) true
        => temp[0] < temp[1] => 10 < 20 true
         => dp[1] = Math.max(1, solution(0)+1) = 2

       solution(2)
       dp[2] = 1
       i = 1 (i >= 0) true
       => temp[1] < temp[2] => 20 < 10 false
       => temp[0] < temp[2] => 10 < 10 false

       solution(3)
       dp[3] = 1
       i = 2 (i >= 0) true
       => temp[2] < temp[3] => 10 < 30 true
        => dp[3] = Math.max(1, solution(2) + 1) = 2
       => temp[1] < temp[3] => 20 < 30 true
        => dp[3] = Math.max(2, solution(1) + 1) = 3
       => temp[0] < temp[3] => 10 < 30 true
        => dp[3] = Math.max(3, solution(0) + 1) = 3

       solution(4)
       dp[4] = 1
       i = 3 (i >= 0) true
       => temp[3] < temp[4] => 30 < 20 false
       => temp[2] < temp[4] => 10 < 20 true
        => dp[4] = Math.max(1, solution(2) + 1) = 2
       => temp[1] < temp[4] => 20 < 20 false
       => temp[0] < temp[4] => 10 < 20 true
        => dp[4] = Math.max(2, solution(0) + 1) = 2
        
       solution(5)
       dp[5] = 1
       i = 4 (i >= 0) true
       => temp[4] < temp[5] => 20 < 50 true
        => dp[5] = Math.max(1, solution(4) + 1) = 3
       => temp[3] < temp[5] => 30 < 50 true
        => dp[5] = Math.max(3, solution(3) + 1) = 4
       => temp[2] < temp[5] => 10 < 50 true
        => dp[5] = Math.max(4, solution(2) + 1) = 4
       => temp[1] < temp[5] => 20 < 50 true
        => dp[5] = Math.max(4, solution(1) + 1) = 4
       => temp[0] > temp[5] => 10 < 50 true
        => dp[5] = Math.max(4, solution(0) + 1) = 4

결과

느낀 점

• 문제를 이해하고 풀고 나면 쉬운 문제인데 처음 문제를 접했을땐 마냥 어렵게만 느껴졌다... 아직 문제를 풀기엔 한참 부족한 것 같다...