[BOJ 18353] 병사 배치하기

병사 배치하기

BOJ 18353 : 병사 배치하기

해설

이 문제는 최장 증가 부분 수열(LIS) 문제로, 부분 수열에 대한 개념과 LIS 알고리즘 풀이 방법을 모른다면 링크를 통해 배우도록 하자.

• ✔ 병사를 배치할 때, 앞쪽에 있는 병사의 전투력이 항상 뒤쪽보다 높아야 한다.
  • ✔ 즉, 최종 결과 안에 전투력이 중복된 병사가 존재하면 안된다.
• ✔ 특정 위치에 있는 병사를 열외 시킨다는 의미
  • ✔ 입력 값이 주어지면 따로 내림차순 혹은 오름차순으로 정렬한 다음 계산하는 것이 아니라, 주어진 입력 값에서 특정 위치에 있는 병사를 제거하여 문제의 조건을 만족하라는 의미

따라서, 주어진 입력 값에서 특정 위치에 있는 병사를 제거하여, 앞쪽에 있는 병사의 전투력이 뒤 쪽에 있는 병사의 전투력보다 높도록 하되, 남아있는 병사의 수가 최대가 되도록 해라

이 문제는, 입력 값을 뒤집어서 LIS 알고리즘을 사용하여 해결할 수 있다.

문제에서 입력 값이 2000 으로 제한되어있기 때문에 O(N^2) 으로 풀어도된다. 만약에 2000이 넘어 갔다고하면 O(NlogN) 방식으로 문제를 풀어야 한다.

구현 : O(N^2)

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

// 병사 배치하기
public class Main {

    static int N;
    static int[] dp;
    static int answer;
    static List<Integer> list = new ArrayList<>();

    public static void main(String[] args) {
        input();
        solution();
        System.out.println(answer);
    }

    static void input() {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        for (int i = 0; i < N; i++) {
            list.add(sc.nextInt());
        }
    }

    static void solution() {
        dp = new int[list.size()];

        Collections.reverse(list);

        // dp 초기화
        for (int i = 0; i < N; i++) {
            dp[i] = 1;
        }

        for (int i = 1; i < list.size(); i++) {
            for (int k = 0; k < i; k++) {
                int prev = list.get(k);
                int next = list.get(i);
                if(next > prev) {
                    dp[i] = Math.max(dp[i], dp[k] + 1);
                }
            }
        }

        // 열외해야 하는 병사의 최소 수를 출력
        int maxValue = 0;
        for (int i = 0; i < N; i++) {
            maxValue = Math.max(maxValue, dp[i]);
        }
        answer = N - maxValue;
    }
}

구현 : O(NlogN)

import java.util.*;

public class Main {

    static int N;
    static int[] dp;
    static int answer;
    static List<Integer> list = new ArrayList<>();

    public static void main(String[] args) {
        input();
        solution();
        System.out.println(getAnswer());
    }

    static void input() {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        for (int i = 0; i < N; i++) {
            list.add(sc.nextInt());
        }
    }

    static void solution() {
        dp = new int[list.size()];

        Collections.reverse(list);

        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = list.get(0);

        int dpIndexByLastUpdated = 0;
        for (int i = 1; i < list.size(); i++) {
            int next = list.get(i);
            int lastValueInDp = dp[dpIndexByLastUpdated];
            if(lastValueInDp < next) {
                dp[++dpIndexByLastUpdated] = next;
            } else {
                int findIndex = binarySearch(0, dpIndexByLastUpdated, next);
                dp[findIndex] = next;
            }
        }
    }

    /**
     * 이진 탐색을 통해서 next 가 dp 의 어느 index 에 들어가야하는지, 알맞은 index 를 찾는다.
     * @param start 0
     * @param end dpIndexByLastUpdated
     * @param target 비교 대상인 다음 값(next)
     */
    static int binarySearch(int start, int end, int target) {
        int index = 0;
        while(start <= end) {
            int middle = (start + end) / 2;

            if(dp[middle] >= target) {
                end = middle - 1;
                index = middle;
            }
            else{
                start = middle + 1;
            }
        }
        return index;
    }

    /**
     * dp 에 Integer.MAX_VALUE 가 아닌 값들에 대해서 개수를 카운트한다.
     */
    static int getAnswer() {
        int count = 0;
        for(int i = 0; i < dp.length; i++) {
            if(dp[i] == Integer.MAX_VALUE) {
                break;
            }
            count++;
        }
        answer = N - count;
        return answer;
    }
}