[백준] 14002

가장 긴 증가하는 부분 수열 4

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

둘째 줄에는 가장 긴 증가하는 부분 수열을 출력한다. 그러한 수열이 여러가지인 경우 아무거나 출력한다.

풀이

const long = () => {
  const [[n], arr] = require("fs")
    .readFileSync("/dev/stdin")
    .toString()
    .trim()
    .split("\n")
    .map((v) => v.split(" ").map(Number));
  let dp = Array.from({ length: n }, (_) => []);
  dp[0].push(arr[0]);
  for (let i = 0; i < n; i++)
    for (let j = 0; j < i; j++) {
      if (dp[j].length >= dp[i].length && arr[i] > arr[j])
        dp[i] = [...dp[j], arr[i]];
      else if (!dp[i].length) dp[i] = [arr[i]];
    }
  let max = [];
  dp.forEach((v) => {
    if (v.length > max.length) max = v;
  });
  console.log(`${max.length}\n${max.join(" ")}`);
};

long();

반성회

11053 문제를 응용하되, 개수를 저장하지 않고 배열을 저장하였다

1. dp 배열을 길이 n의 배열로 초기화한다 (각 원소는 빈 배열로 초기화)
2. dp[0] 은 [arr[0]] 으로 초기화한다 (유일한 부분수열)
3. i를 0부터 n 전까지 순회하여 dp[i]를 채운다
   • dp[i] 를 채우기 위해, j를 0부터 i 전까지 순회하여 dp[0]부터 dp[i - 1]까지 체크한다
   • dp[0] 부터 dp[i - 1] 까지 (0 ≤ j < i) 의 배열 중 길이가 가장 긴 것을 찾는다 (탐색 방법은, 큰 값이 나올 때마다 dp[i] 를 매번 갱신한다)
   • 이때 arr[i]가 arr[j] 보다 커야 ‘증가하는 부분 수열’ 조건을 만족하므로, 조건문에 더한다
   • 만약 0 ≤ j < i 범위까지의 dp[j] 중 arr[i] > arr[j] 조건을 만족하는 dp[j]가 존재하지 않아 dp[i]가 빈 배열일 경우, dp[i] = [arr[i]] 로 초기화한다 (초기화하지 않으면 부분 수열이 비어있는 문제가 발생)
4. dp[i] 를 다 채웠을 경우, 그 중에서 길이가 가장 긴 배열을 찾는다 (max)
5. max의 길이와 원소들을 개행을 기준으로 출력한다

틀린 이유는 중간에 dp[i] = [arr[i]] 초기화 부분이 없어서였다

dp[0]은 [arr[0]]으로 초기화되니까 만약 dp[j]가 dp[0]의 원소를 포함할 경우엔 값이 정상적으로 포함되지만, 중간에 dp[i]를 초기화하지 않으면 조건을 만족하는 dp[j]가 없을 경우 dp[i]가 빈 배열로 남아있는 경우가 있다

이렇게 되면 그 뒤에 계산되는 부분수열 중 dp[i]를 포함하는 수열을 정상적으로 계산해줄 수 없으므로 초기화가 필수