[Javascript] 백준 11053: 가장 긴 증가하는 부분 수열

문제

수열 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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

예제 입력 1 

6
10 20 10 30 20 50

예제 출력 1 

4

 

---

문제 풀이

1. 길이가 N이고 1로 채운 dp배열을 만듭니다.

• dp[i]는 처음부터 i까지의 배열에서 가장 긴 증가하는 부분 수열입니다.
• 모든 dp[i]는 최소 자기 자신으로만 이루어진 수열을 만들 수 있으므로 기본값은 1로 가득 채운 것입니다.
• 예제 [10, 20, 10, 30, 20, 50]로 설명하자면,
  • dp[1] : [10]에서 가장 긴 증가하는 수열의 길이는 1이다.
  • dp[2] : [10, 20]에서 가장 긴 증가하는 수열의 길이는 2이다.
  • dp[3] : [10, 20, 10]에서 가장 긴 증가하는 수열의 길이는  dp[2]에서 구한 수열이고, 따라서 여전히 2이다.
  • dp[4] : [10, 20, 10, 30]에서 가장 긴 증가하는 수열의 길이는 3이다. 이는 이전의 dp들에서 가장 긴 dp[2]의 수열에서 30이 추가 됨에 따라 길이가 3이 된 것이다.
• 여기서 규칙을 찾아보면, dp[i]는 주어진 원본 수열 arr의 i-1까지의 배열 즉 현재의 나 이전의 값들로 이루어진 배열에서 나보다 작은 값들의 DP값 중 가장 큰 값을 더한 값입니다.

 

2. 원본 배열을 처음부터 순회하며, 현재 값 이전까지의 값으로 이루어진 배열을 생성합니다(prevArr).

3. 이전의 배열들의 값 중 나보다 작은 값들의 dp중 가장 큰 값을 가져와야하므로, 임시 배열(temp)를 생성합니다.

4. prevArr를 순회하며 현재의 나보다 작은 값이라면 temp에 dp값을 푸시해줍니다.

5. 그 중 가장 큰 값을 찾아 dp[i]에 더해줍니다.

6. 끝까지 반복 후 dp 중 가장 큰 값을 출력해줍니다.

 

 

const input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n")
  .map((v) => v.split(" ").map(Number));

const [N, arr] = input;

const dp = Array(...N).fill(1);

for (let i = 1; i < N; i++) {
  const prevArr = arr.slice(0, i);
  const temp = [];

  for (let j = 0; j <= i; j++) {
    if (prevArr[j] < arr[i]) {
      temp.push(dp[j]);
    }
  }

  if (temp.length !== 0) {
    dp[i] += Math.max(...temp);
  }
}

console.log(Math.max(...dp));