백준 14002 - 가장 긴 증가하는 부분수열

문제 풀이에 집중하기 보다는, 부분수열을 구하는 데에 가져야 하는 생각을 정리해 보았습니다

문제

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

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

풀이

해당 문제는 dp를 이용해야 시간 초과 없이 풀 수 있다

const A = [10,20,10,30,20,50]

• 0번째 인덱스(10)

하나밖에 없기 때문에 부분수열도 하나일 것이다 => [10]

• 첫번째 인덱스(20)

0번째 원소인 10보다 20이 더 크기때문에 하나의 부분수열을 만들 수 있게 된다 => [10,20]

• 두번째 인덱스(10)

0번째, 1번째 원소보다 크지 않기 때문에 부분수열을 만들 수 없나? 라고 할 수도 있지만

[10,20,1,2,3,4,5,6,7,...] 일 경우에는 저 1부터 시작하는 것이 가장 긴 부분수열이 될 수 있다

그렇기 때문에 만들 수 있는 부분수열은 자기 자신인 [10]이다

• 세번째 인덱스(30)

이제부터는 하나하나씩 따져보는게 아니라 한번 앞의 계산값의 관점에서 살펴보겠다
이전에 만들어졌던 부분수열을 보면

[10] //0
[10,20] //1
[10] //2

우리는 부분수열의 경우의 수를 찾는게 아니라 가장 긴 부분수열만을 만들면 된다

그렇다는 건 증가한다는 조건만 맞으면
기존에 구해놨던 부분수열 중 가장 긴 부분수열에 + 현재 인덱스에 해당하는 원소를 넣어주는게 가장 긴 부분수열이 될 것이다

이 경우 세번째 인덱스에서 만들 수 있는 가장 긴 부분수열은 1번째에서 만들었던 부분수열에 +30을 추가한 [10,20,30] 이 될 것이다

여기서 dp를 이용하는 감을 잡을 수 있었는데

dp[i] = i번째 인덱스까지의 원소로 만들 수 있는 가장 길면서 증가하는 부분수열

const dp = Array.from(Array(n + 1), () => [])

dp[0] = [arr[0]]

for (let i = 1; i < n; i++) {
  let max = 0
  let result = []
  for (let j = 0; j < i; j++) {
    if (arr[i] > arr[j]) {
      if (dp[j].length > max) {
        max = dp[j].length
        result = dp[j]
      }
    }
  }
  dp[i] = [...result, arr[i]]
}

예시를 또 들어보면

수열 = 10 20 10 30

dp[3] 을 구하기 위해서 0~2 번째 인덱스까지 구할 수 있는 부분수열 중에서,
1. 30 이라는 수가 들어가도 증가하는 부분수열이라는 규칙이 성립하는 게 있는지를 조사하고
2. 그 중에서도 가장 긴 부분수열을 찾아서 그 부분수열에 + 3번째 원소를 하는것이 효율적일 것이라는 이야기이다

1번을 충족하기 위해서는 dp가 아니라 일반 수열의 값만 비교해봐도 알 수 있다

수열[j] < 수열[i] 라면 (i>j 일 경우) dp[j]에 수열[i] 가 들어가도 괜찮다

2번을 충족하기 위해서는 dp[0~j] 의 길이들을 각각 조사해서, 그 중 가장 긴 값을 찾아야 한다

• 왜냐하면 0~j 중에 어떤 게 가장 긴 부분수열일지는 모르기 때문에

최종적으로 dp[i] = [...최종적으로 찾은 부분수열,수열[i]] 를 해주면 된다

코드

const input = require("fs").readFileSync("./input.txt").toString().trim().split("\n")
const n = +input[0]
const arr = input[1].split(" ").map(v => +v)

const dp = Array.from(Array(n + 1), () => [])

dp[0] = [arr[0]]

for (let i = 1; i < n; i++) {
  let max = 0	// 이 값을 통해서 0~j까지의 부분 수열중에 가장 긴 부분수열을 찾을 수 있다
  let result = []
  for (let j = 0; j < i; j++) {
    if (arr[i] > arr[j]) {
      if (dp[j].length > max) {
        max = dp[j].length 
        result = dp[j]
      }
      
    }
  }
  dp[i] = [...result, arr[i]]
}

dp.sort((a, b) => a.length - b.length)
console.log(dp.at(-1).length)
console.log(dp.at(-1))