백준 18353 병사배치하기 (LDS)

백준 18353 병사배치하기

LIS (Longest Increasing Subsequence), ‘최장 증가수열’

LDS (Longest Decreasing Sequence), ‘최장 감소수열’

같은 로직이고, 수열이 증가하냐 감소하냐의 차이이다.

---

public class Main_bj_18353_병사배치하기 {
    public static void main(String[] args) throws IOException {
        // input
        System.setIn(new FileInputStream("solveProblem/res/Main_bj_18353_병사배치하기.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // init
        int n = Integer.parseInt(br.readLine());
        int[] dp = new int[n];
        int[] soldiers = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            soldiers[i] = Integer.parseInt(st.nextToken());
            dp[i] = 1;
        }

        // solve (LIS)
        for (int i = 1; i < n; i++) {
            for(int j = 0; j < i; j++) {
                if(soldiers[i] < soldiers[j]) 
                    dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }

        // result
        Arrays.sort(dp);
        System.out.println(n - dp[n-1]);
    }
}

문제에서 구하고자하는 부분수열은 내림차순 이므로 soldiers[i] < soldiers[j] 가 된다. (LDS)

오름차순 일때는 soldiers[i] > soldiers[j] 가 된다. (LIS)

Test

#1

input :
7
15 11 4 8 5 2 4

15 11 8 5 2 또는, 15 11 8 5 4 의 경우에 길이 5인 최장 감소수열을 찾을 수 있다.

#2

input :
20
1 2 3 10 9 8 2 1 5 4 7 6 5 15 14 13 12 1 10 9

10 9 8 7 6 5 1 의 경우에 길이 7인 최장 감소수열을 찾을 수 있다.

---

LIS 예제 : 백준 11053 가장 긴 증가하는 부분 수열

LDS 예제 : 백준 11722 가장 긴 감소하는 부분 수열

---

n이 10만을 넘는다면 ?

O(nlog n) - 1

이분 탐색과 lower_bound

O(nlog n) - 2

세그먼트 트리