[BOJ] 11053 가장 긴 증가하는 부분 수열 - JAVA

1. 문제

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

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

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

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

---

2. 풀이

• 전에 푼 적이 있어서 풀이가 두 개다. 둘 다 소개한다.

list 이용하는 방법

• 입력받은 배열이 {10,20,5,10,30,25}라고 할 때, 리스트에 순서대로 하나씩 집어넣는다.
• 첫 번째 원소는 비교 없이 넣는다.
• 두 번째 원소부터는 리스트의 가장 끝 값과 비교하고 끝 값보다 현재 원소 값이 더 크다면 끝에 더한다.
• Collections.binarySearch는 해당 값이 "정렬된" list에 없다면 -삽입해야되는 위치-1을 반환한다. 이 함수를 이용해서 만약 끝값보다 현재 원소값이 크지 않다면 binarySearch로 현재 원소 값이 어느 위치로 가야 하는지 알아낸다. 그 위치의 원소를 현재 원소로 바꿔치기한다. 이 때, 이미 있는 원소라면(처음 반환값이 >= 0) 따로 교체하지 않고 다음 원소 비교로 넘어간다.
• 이렇게 하는 이유는, 끝 값을 그대로 보존하면서 새 경우의 수를 찾기 위함이다. 끝 값이 그대로 남아있으니 비교하면서 계속 이어갈 수도 있고, 그림의 4번과 6번 경우처럼 길이가 같은데도 끝 값이 더 작은 새로운 수열이 만들어질 수도 있다. 길이가 같은데 끝 값이 작으면 클 때보다 더 많은 수가 더해질 수 있는 가능성이 있다.

 

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

public class BOJ_11053_가장긴증가하는부분수열 {
   public static void main(String[] args) throws IOException {
      BufferedReader in =new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st;

      int N = Integer.parseInt(in.readLine());
      int[] A = new int[N];

      st = new StringTokenizer(in.readLine());
      for(int i=0;i<N;i++) A[i] = Integer.parseInt(st.nextToken());

      List<Integer> list = new ArrayList<>();
      list.add(A[0]);

      for(int i=1;i<N;i++){
         if(list.get(list.size()-1)<A[i]) {
            list.add(A[i]);
            continue;
         }
         int idx = Collections.binarySearch(list, A[i]); //(-(insertion point) - 1).
         if(idx>=0) continue;
         idx = -idx-1;
         list.set(idx,A[i]);
      }

      System.out.println(list.size());
   }
}

 

앞을 모두 탐색하는 방법

• LIS배열에는 길이, sequence배열에는 수열 값을 넣는다.
• subsequence(n)함수는 n번째 LIS배열의 값을 반환한다.
  • 먼저 LIS[n]에 1을 넣는다.
  • LIS[0]부터 LIS[n-1]까지 탐색하며 값이 sequence[n]보다 작으면서 길이도 LIS[n]보다 크거나 같은 값을 찾는다. 
  • sequence[n]보다 작아야 그 뒤를 이어갈 수 있고, 최소 길이가 LIS[n]보다 같거나 더 커야 가장 긴 값 LIS[n]에 담을 수 있다. 같은 값도 찾는 이유는 어차피 LIS[n]에 찾은 길이+1을 하기 때문이다. (n번째 원소를 추가한다는 의미다.)
• subsequence함수 마지막에 max 값을 비교하면서 어떤 값이 가장 큰지 저장해둔다.

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

public class Main {
   static int[] sequence;
   static int[] LIS;
   static int max = Integer.MIN_VALUE;

   public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      int n = Integer.parseInt(br.readLine());

      sequence = new int[n + 1];
      LIS = new int[n + 1];

      StringTokenizer st = new StringTokenizer(br.readLine(), " ");
      for (int i = 1; i < n; i++) sequence[i] = Integer.parseInt(st.nextToken());

      subsequence(n);
      System.out.println(max);
   }

   public static void subsequence(int n) {
      if (n < 1) return;
      if (LIS[n] != 0) return;

      subsequence(n - 1);

      LIS[n] = 1;

      for (int i = 1; i < n; i++) {
         int length = LIS[i];

         //값이 나보다 작고 길이가 나보다 길거나 같으면
         if (sequence[i] < sequence[n] && length >= LIS[n]) {
            LIS[n] = length + 1;
         }
      }

      if (max < LIS[n]) max = LIS[n];
   }


}

---

3. 결과

가장 아래에 있는 코드가 앞을 모두 탐색한 결과다. (배열 이용)