[BOJ 1965] 상자넣기

문제

상자넣기

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

 

 

풀이

설명

한 줄에 넣을 수 있는 상자의 최대 개수를 구하는 문제입니다.

 

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

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

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 boxes = input().split(" ").map(Number);
  const dp = Array(n).fill(1);

  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (boxes[j] < boxes[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
    }
  }

  return Math.max(...dp);
}

 

이분탐색

function solution() {
  const n = Number(input());
  const boxes = input().split(" ").map(Number);
  const lis = [boxes[0]];

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

  return 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;
  }
}