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

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

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

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        int[] dp = new int[N];
        Arrays.fill(dp, 1);

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        for (int i = 1; i < N; i++){
            int x = arr[i];
            for (int j = 0; j < i; j++){
                int y = arr[j];
                if (x > y) dp[i] = Math.max(dp[j] + 1, dp[i]);
            }
        }
        int max = 0;
        System.out.println(Arrays.stream(dp).max().getAsInt());
    }
}

1. 어려웠던 점:

- DP 문제를 풀 때마다, DP 배열이 무엇을 의미하는지를 정하는 것이 어렵다.

2. 알게된 점:

- DP 문제 연습

- Stream을 처음 사용 해보았다.

 

3. 알고리즘 풀이:

- DP 배열은 그 자신을 사용하면서 가장 긴 증가하는 부분 수열이다.

즉 DP[i]는 arr[i]의 값이 포함되는 가장 긴 증가하는 부분 수열을 의미한다.

arr	30	40	50	0	10	20	30	40
dp	1	2	3	1	2	3	4	5

arr	10	20	10	30	20	50
dp	1	2	1	3	2	4

dp 배열은 자기 자신을 포함하는 부분 수열이기 때문에 전부 최소 1이 될 수 있다. 

때문에 전부 1로 초기화 해준다.

 

자신보다 아래 칸에 위치한 arr값과 비교한 후,

더 크면 그 dp값에 1을 올려 현재 dp값과 비교한다.

즉 i가 3이면 i가 1인 arr의 값과 비교.

i가 1인 arr값이 더 크다면, dp[3] = Math.max(dp[1] + 1, dp[3])

i가 2인 값과도 비교.

 

이를 모든 dp배열에 수행하고

dp배열 중 가장 큰 값이 가장 긴 증가하는 부분 수열이 된다.