[백준] 11722번 : 가장 긴 감소하는 부분 수열

문제

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

예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에

가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} 이고, 길이는 3이다.

입력

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

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

출력

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

문제해결방법

먼저 이 문제를 해결하기 전에 LIS를 살펴보자.

LIS를 푸는 방법은 두 가지가 있다.

첫 번째 방법은 DP를 이용해서 푸는 방법이다.

현재 위치보다 앞에 있는 숫자들 중에 현재 숫자보다 값이 작은 수들의 DP값 중 최대 + 1

두 번째 방법은 증가하는 부분 수열을 만드는 수열들 중에 최적인 수열을 관리하는 배열 LIS을 만드는 것이다.

부분 수열의 마지막에 붙이려는 숫자가 LIS의 마지막 원소보다 크면, LIS의 배열의 마지막에 추가한다.

만약 작다면 LIS 배열 중에 붙이려는 숫자보다 큰 수들 중에 가장 앞에 있는 수(Lower Bound)와 교체해준다.

이번 문제는 위 방법 중 두 번째 방법을 약간 변형해서 풀었다.

코드

package baekjoon;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
 
public class Main11722_가장긴감소하는부분수열 {
 
    public static int N;
    public static List<Integer> lds = new ArrayList<>();
    
    public static int upperLimit(List<Integer> list, int num) {
        int si = 0, ei = list.size()-1;
        while(si<=ei) {
            int mi = (si+ei)/2;
            if(list.get(mi)<num) ei = mi-1;
            else if (list.get(mi)>num) si = mi+1;
            else return mi;
        }
        return si;
    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        lds.add(0);
        for(int i=0; i<N; i++) {
            int num = Integer.parseInt(st.nextToken());
            if(lds.get(lds.size()-1)>num) lds.add(num);
            else {
                int index = upperLimit(lds, num);
                lds.set(index, num);
            }
        }
        System.out.println(lds.size());
    }
}

코드에 대한 피드백이나 더 좋은 아이디어는 언제나 환영입니다.