[BOJ/백준] 11053 가장 긴 증가하는 부분 수열 (S2)

문제

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

풀이

이 문제는 DP 문제, LIS를 이용해서 푸는 문제이다.

LIS (Longest Increasing Subsequence) : 최장 증가 부분 수열
: 주어진 수열에서 오름차순으로 정렬된 가장 긴 부분 수열을 찾는 알고리즘

 

문제에서 주어진 수열을 보면 arr = {10, 20, 10, 30, 20, 50}이므로 수열을 담는 배열인 arr[]과 dp 값을 설정하는 배열인 dp[]를 생성한다. 그리고 수열을 입력받으면서 dp 배열의 값들을 1로 초기화한다.

1. dp 배열을 초기화하면 각 위치에서 최소 길이는 1이다. → dp = {1, 1, 1, 1, 1, 1}
2. i = 2일 때, arr[2] = 20이다.
   • j = 1에서 arr[2] > arr[1]이므로 dp[2] = Math.max(dp[2], dp[1] + 1) = Math.max(1, 2) = 2이다.
   • dp = {1, 2, 1, 1, 1, 1}
3. i = 3일 때, arr[3] = 10이다.
   • j = 1에서 arr[3] <= arr[1]이므로 아무것도 하지 않는다.
   • j = 2에서도 arr[3] <= arr[2]이므로 아무것도 하지 않는다.
   • dp = {1, 2, 1, 1, 1, 1} (변화 없음)
4. i = 4일 때, arr[4]  = 30이다. 
   • j = 1에서 arr[4] > arr[1]이므로 dp[4] = Math.max(dp[4], dp[1] + 1) = Math.max(1, 2) = 2가 된다. → dp = {1, 2, 1, 2, 1, 1}
   • j = 2에서 arr[4] > arr[2]이므로 dp[4] = Math.max(dp[4], dp[2] + 1) = Math.max(2, 3) = 3이 된다. → dp = {1, 2, 1, 3, 1, 1}
   • j = 3에서 arr[4] > arr[3]이므로 dp[4] = Math.max(dp[4], dp[3] + 1) = Math.max(3, 2) = 3이 된다. → dp = {1, 2, 1, 3, 1, 1}
   • dp = {1, 2, 1, 3, 1, 1}
5. i = 5일 때, arr[5] = 20
   • j = 1에서 arr[5] > arr[1]이므로 dp[5] = Math.max(dp[5], dp[1] + 1) = Math.max(1, 2) = 2가 된다. → dp = {1, 2, 1, 3, 2, 1}
   • j = 2에서 arr[5] <= arr[2]이므로 아무것도 하지 않는다. → dp = {1, 2, 1, 3, 2, 1}(변화 없음)
   • j = 3에서 arr[5] > arr[3]이므로 dp[5] = Math.max(dp[5], dp[3] + 1) = Math.max(2, 2) = 2가 된다. → dp = {1, 2, 1, 3, 2, 1}
   • j = 4에서도 arr[5] <= arr[4]이므로 아무것도 하지 않는다. → dp = {1, 2, 1, 3, 2, 1}
   • dp = {1, 2, 1, 3, 2, 1}
6. i = 6일 때, arr[6] = 50
   • j = 1에서 arr[6] > arr[1]이므로 dp[6] = Math.max(dp[6], dp[1] + 1) = Math.max(1, 2) = 2가 된다. → dp = {1, 2, 1, 3, 2, 2}
   • j = 2에서 arr[6] > arr[2]이므로 dp[6] = Math.max(dp[6], dp[2] + 1) = Math.max(2, 3) = 3가 된다. → dp = {1, 2, 1, 3, 2, 3}
   • j = 3에서 arr[6] > arr[3]이므로 dp[6] = Math.max(dp[6], dp[3] + 1) = Math.max(3, 2) = 3가 된다. → dp = {1, 2, 1, 3, 2, 3}
   • j = 4에서 arr[6] > arr[4]이므로 dp[6] = Math.max(dp[6], dp[4] + 1) = Math.max(3, 4) = 4가 된다. → dp = {1, 2, 1, 3, 2, 4}
   • j = 5에서 arr[6] > arr[5]이므로 dp[6] = Math.max(dp[6], dp[5] + 1) = Math.max(4, 3) = 4가 된다. → dp = {1, 2, 1, 3, 2, 4}
   • dp = {1, 2, 1, 3, 2, 4}

결국, dp 배열은 dp = {1, 2, 1, 3, 2, 4}이 되며 가장 긴 증가하는 부분 수열의 길이는 4가 된다.

Code

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        int arr[] = new int[N+1];  // 수열
        int dp[] = new int[N+1];  // dp

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            dp[i] = 1;  // 일단 dp값들은 최소 1
        }
        int max = 1;
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j < i; j++) {
                if (arr[i] > arr[j]) {  // arr의 현재값이 이전 값보다 크면
                    // 각 i에 대해 가능한 모든 j를 검사하고, 그 중 가장 긴 증가하는 부분 수열의 길이를 dp[i]에 다시 저장하므로
                    // max()로 dp[i]를 계속 비교함
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            max = Math.max(max, dp[i]);  // 최댓값 저장
        }
        bw.write(max + "");
        bw.flush();
        bw.close();
    }
}