[백준 11053 java 자바]가장 긴 증가하는 부분 수열 (DP)

[Silver II] 가장 긴 증가하는 부분 수열 - 11053

문제 링크

성능 요약

메모리: 11944 KB, 시간: 100 ms

분류

다이나믹 프로그래밍(dp)

문제 설명

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

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

입력

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

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

출력

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

---

풀이

dp문제는 항상 그렇듯, dp에 어떤 것을 담느냐는 개념이 중요한 것 같다. 나는 주로 bottom-up으로 풀기에 왼쪽부터 오른쪽 방향으로 진행하면서 데이터를 갱신할 방법을 찾는다. 이번에 원하는 정보는 증가하는 부분 수열. dp에 증가한 부분 수열을 담으면 된다.

ex) 10, 20, 10, 30, 20, 50인 경우,
dp[1] = (10) = 1
dp[2] = (10,20) dp[1] 까지 20보다 작은 수 중에 가장 큰 dp값 + 1 (자기 자신) = dp1 + 1
dp[3] = (10)dp[1],dp[2] 까지 10 보다 작은 수의 dp 값에 + 1 (없으므로 그냥 초기화값) = 1
dp[4] = (10,20,30)dp[1]

dp[3] 까지 30 보다 작은 수의 dp 값에 + 1 / dp[2]가 30보다 작은 20이면서 (10,20) 으로 가장 긴 증가하는 수열을 가지고 있다. 거기에 자기 자신 +1 = dp2 + 1
dp[5] = dp[1]

dp[4] 까지 20보다 작은 수 dp[1],dp[3] 둘 다 1이므로 dp[5]는 2 (10,20)
dp[6] = dp[1]~dp[5] 까지 50보다 작은 수 중에 가장 큰 dp 값을 가진 것은 dp[4] (10,20,30 + 50) 최종 길이는 4이다.

결과적으로 현재 자신의 왼쪽에 있는 작은 수들의 길이 중에 가장 긴 수열 + 자기 자신 포함한 것을 자기 자신의 dp에 저장한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N;
    static int[] arr;
    static int[] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N+1];
        dp = new int[N+1];
        String[] strs = br.readLine().split(" ");
        int len = strs.length;
        for (int i = 1; i <= len; i++) {
            arr[i] =Integer.parseInt(strs[i-1]);
            dp[i] = 1; //중요, 각 기본 dp 값을 1로 설정(자기 자신 길이 포함)
        }
        int result = 1;
        for (int i = 1; i <= len; i++) { //전체 수열의 길이만큼 반복
            for (int j = 1; j < i; j++) { //현재 수열 값에 좌측의 모든 값들 중, 나보다 작으면서 가장 큰 dp 값에 자기 자신 + 1 vs 지금값
                if (arr[j] < arr[i]) {
                    dp[i] = Math.max(dp[j]+1, dp[i]);
                }
            }
            result = Math.max(result,dp[i]);
        }
        System.out.println(result);
    }
}