BOJ - 18353 병사 배치하기

1. 문제 : https://www.acmicpc.net/problem/18353

2. 문제 유형 : Dynamic Programming

3. 문제 티어 : 실버 2

4. 문제 풀이 

 - 병사의 최대 수를 물어보기 때문에 LIS 알고리즘을 고려해야 한다. 

( 최대 수 , 최장 길이 , 가장 많은 .. 등이 들어갈 때 LIS 알고리즘을 고려해보자) 

- LIS 알고리즘을 고려하기 위해 DP와 이진탐색 두 가지 방법이 있다. 여기서 나는 이진탐색 방법을 선택했다.
(복잡한 대신 더 속도가 빠르고 효율적이기 때문이다.)

* LIS 알고리즘이란?
최장 증가 부분 수열(LIS)라고 하며 주어진 수열에서 일부 숫자들을 선택하여 만든 증가하는 부분 수열 중 가장 길이가 긴 수열을 찾는 방법이다.

ex) 수열 : [10, 20, 10, 30, 20, 50] 
  - 가능한 증가 부분 수열 : 
        - [10], [10, 20], [10, 30], [10, 20, 30], [10, 20, 50] 등

  - 최장 증가 부분 수열:
        - [10, 20, 30, 50] (길이 4)

 

- 이 문제를 풀려면 LIS 알고리즘의 선행 조건인 증가하는 부분으로 만들어줘야 하기 때문에 내림차순인 병사 집단을 오름 차순으로 변환해야 하는 것이 가장 핵심 접근법이라고 할 수 있다. 
따라서 문제 풀이 순서는 아래와 같다.
1) N과 병사 수가 담겨 있는 arr 값 입력받음
2) arr를 오름차순으로 변환해줌
3) LIS 알고리즘 함수 작성
4) LIS 알고리즘 함수를 작성하기 위한 이진 탐색 lowerBound 함수 작성

5) 제거할 병사의 수를 구하는 것이므로 역순으로 다시 N에서 최장 길이를 빼줘야 함

 

5. 코드

1) N과 병사 수가 담겨 있는 arr 값 입력 받음

// 값 입력 받음
const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");
let N = Number(input[0]);
let arr = input[1].split(" ").map(Number);

 

2) arr를 오름차순으로 변환해줌

// arr를 오름차순으로 변환함
arr.reverse();

 

3) LIS 알고리즘 함수 작성

function LIS(arr) {
    const list = []; // LIS를 구성하는 배열
    for(let x of arr){
        const pos = lowerBound(arr,x); // x가 들어갈 위치를 찾음
        // 만약 위치가 제일 끝이면
        if(pos === list.length) {
            list.push(x); // 새 원소를 추가해줌
        } else {
            list[pos] = x; // 기존 원소를 x로 교체
        }
    }
    return list.length; // LIS의 최장 길이를 반환
}

 

4) LIS 알고리즘 함수를 작성하기 위한 이진 탐색 lowerBound 함수 작성

function lowerBound(arr, target) {
    let left = 0;
    let right = arr.length;
    while(left < right) {
        const mid = Math.floor((left + right) / 2);
        // 만약 중간 값이 target보다 작다면
        if(arr[mid] < target) left = mid + 1; // 한 칸 오른쪽으로 이동 시켜줌
        else right = mid; // target 보다 크다면 끝 범위를 mid로 축소 시켜줌
    }
    return left; // target이 들어갈 위치
 }

 

5) 제거할 병사의 수를 구하는 것이므로 역순으로 다시 N에서 최장 길이를 빼줘야 함

console.log(N - LIS(arr));

 

 

6. 시간 복잡도

 

• 입력 처리 및 배열 뒤집기: O(N)
• LIS 알고리즘:
  • 각 원소에 대해 이분 탐색 수행 (O(log⁡N)
  • 총 NNN개의 원소를 처리하므로 O(Nlog⁡N)
• 전체 복잡도: O(Nlog⁡N)

7. 전체 코드

const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");
let N = Number(input[0]);
let arr = input[1].split(" ").map(Number);
// arr 뒤집음
arr.reverse();
// 병사 수가 최대로 남아야 하기 때문에 최장 증가 거리 수열 찾는 LIS 알고리즘 
function LIS(arr) {
    const list = [];
    for(let x of arr){
        const pos = lowerBound(list, x);
        if(pos === list.length){
            list.push(x);
        } else {
            list[pos] = x;
        }
    }
    return list.length;   
}

// 이진 탐색 함수
function lowerBound(arr, target) {
    let left = 0;
    let right = arr.length;
    while(left < right) {
        let mid = Math.floor((left + right) / 2);
        if(arr[mid] < target) left = mid + 1;
        else right = mid;
    }
    return left;
}

// arr을 LIS 알고리즘으로 순회 
console.log(N - LIS(arr));