Coding Problem

[BOJ 2631] 줄 세우기

Yepchani 2025. 2. 11. 16:00
반응형

문제

줄 세우기

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

 

 

풀이

설명

아이들을 번호 순서대로 줄을 세울 때, 움직여야 하는 아이의 최소 수를 구하는 문제입니다.

 

LIS(Longest Increasing Subsequence, 최장 증가 부분 수열)를 구하면 됩니다.

lis를 구한 후, 전체 수에서 lis의 길이를 빼면 움직여야 하는 아이의 최소 수가 됩니다.

 

다음 두 가지 방법이 있습니다.

  1. DP
    dp[i]는 i번째까지 셌을 때, lis의 길이입니다.
    dp[i] = Math.max(dp[i], dp[j] + 1);
  2. 이분탐색
    수열을 순회하면서 원소를 lis의 적합한 위치에 넣어줍니다.

 

두 방법 모두 lis를 이용하므로 접근 방법은 비슷하지만, 실행시간에 차이가 있습니다.

DP로 풀 경우, O(N^2)이 걸립니다.

이분탐색으로 풀 경우, O(N logN)이 걸립니다.

 

예시 코드

DP

function solution() {
  const n = Number(input());
  const nums = Array.from({ length: n }, () => Number(input()));
  const dp = Array(n).fill(1);
  
  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
    }
  }
  
  const k = Math.max(...dp);

  return n - k;
}

 

이분탐색

function solution() {
  const n = Number(input());
  const nums = Array.from({ length: n }, () => Number(input()));
  const lis = [nums[0]];

  for (let i = 1; i < n; i++) {
    const num = nums[i];
    if (num > lis.at(-1)) lis.push(num);
    else {
      const pos = binarySearch(num);
      lis[pos] = num;
    }
  }

  return n - lis.length;

  function binarySearch(num) {
    let left = 0,
      right = lis.length;

    while (left < right) {
      const mid = Math.floor((left + right) / 2);
      if (lis[mid] < num) left = mid + 1;
      else right = mid;
    }

    return left;
  }
}