Baekjoon | Q.11053 - 가장 긴 증가하는 부분 수열

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

 주어진 수열에서 가장 긴 증가하는 부분 수열(Longest Increasing Subsequence, LIS)을 찾는 문제이다. LIS란 주어진 수열이 {10, 20, 50, 20, 30, 40, 60, 10, 80} 이라면 {10, 20, 30, 40, 60, 80}을 뜻한다. 

import java.util.Scanner;

public class Main {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] arr = new int[n];
    int[] dp = new int[n];
    for (int i = 0; i < n; i++) {
      arr[i] = sc.nextInt();
    }
    sc.close();

    int answer = 0;

    for (int i = 0; i < n; i++) {
      int now = arr[i];
      int max = 0;

      dp[i] = 1;

      for (int j = 0; j < i; j++) {
        if(now > arr[j] && max < dp[j]) {
          max = dp[j];
        }
      }
      
      dp[i] = max + 1;

      if(dp[i] > answer) answer = dp[i];
    }

    System.out.println(answer);

  }
}

 동적 프로그래밍을 이용하여 문제를 해결했다. dp[i]는 arr[i]로 끝나는 LIS의 길이를 의미한다.

 

dp[i]를 구하기 위해서는 arr[i]보다 작은 수인 arr[j] 중에서 dp[j]의 값이 최대인 수에 1을 증가시켜주면 된다. 

 

수열 {10, 20, 50, 20, 30, 40, 60, 10, 80}을 예시로 살펴보자.

i	0	1	2	3	4	5	6	7	8
arr[i]	10	20	50	20	30	40	60	10	80
dp[i]	1	2	3	2	3	4	5	1	6

LIS의 길이는 dp[]의 수 중에서 최대값을 찾으면 된다.