[JavaScript] 백준 14002 가장 긴 증가하는 부분 수열 4 (JS)

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

📚 문제 설명

수열 A 가 주어졌을 때, 가장 긴 증가하는 부분 수열을 찾아라.

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

👨🏻‍💻 풀이 과정

이 문제는 이전에 풀었던 가장 긴 바이토닉 부분 수열 문제와 백준에 있는 가장 긴 증가하는 부분 수열 문제와 거의 똑같은 문제이다.
따라서 해당 문제에서 사용했던 점화식을 거의 그대로 사용하면 된다.

다만, 이 문제에서는 부분 수열을 직접 보여줘야 한다는 점이 다르기 때문에 조금 응용을 해줘야 한다.

dp[i]는 Numbers의 i번쨰 숫자까지 확인했을 때의 가장 긴 부분 수열.

• dp 배열에 수열을 직접 저장.
• max 변수를 이용해 가장 긴 부분 수열을 저장.

전체 로직은 아래와 같은 과정을 반복문을 통해 반복하며 진행하면 된다.

ex)  i = 3 일 경우.

j = 0
 [10, 20, 10, 30, 20, 50]
   ^           ^
   j           i
dp[j] 배열에 뒤에 30을 추가 가능. ( 10 < 30 이기 때문에 )
dp[i].length < dp[j].length + 1 이기 떄문에 갱신 진행.
dp[i] = [...dp[j], 30] 

j = 1
 [10, 20, 10, 30, 20, 50]
       ^       ^
       j       i
dp[j] 배열에 뒤에 30을 추가 가능. ( 20 < 30 이기 때문에 )
dp[i].length < dp[j].length + 1 이기 떄문에 갱신 진행.
dp[i] = [...dp[j], 30] 

j = 2
 [10, 20, 10, 30, 20, 50]
           ^   ^
           j   i
dp[j] 배열에 뒤에 30을 추가 가능. ( 10 < 30 이기 때문에 )
하지만, dp[i].length < dp[j].length + 1 이 아니다. 
따라서 갱신 X

전체 풀이

    let fs = require("fs");
    let input = require("fs").readFileSync(0, 'utf-8').toString().trim().split("\n");

    const N = parseInt(input.shift());
    const Numbers = input[0].split(' ').map(Number);
	
    let dp = Array.from({length: N}, _ => []);
	// dp 배열 초기화.
    for (let i = 0; i < dp.length; i++) {
        dp[i] = [Numbers[i]];
    }
	// 최댓값 초기화 N = 1인 경우를 위해.
    let max = [1, dp[0]];
	// dp 배열 갱신을 위해 2중 for문 진행.
    for (let i = 1; i < N; i++) {
        for (let j = 0; j < i; j++) {
          	// 증가하는 수열이어야하기 때문에.
            if (Numbers[i] > Numbers[j]) {
              	// 가장 긴 값만 저장하기 위해.
                if (dp[i].length < dp[j].length + 1) {
                    dp[i] = [...dp[j], Numbers[i]];
                }
            }
        }
      	// 최댓값 갱신.
        if (dp[i].length > max[0]) {
            max = [dp[i].length, dp[i]];
        }
    }
	// 정답 출력.
    let answer = `${max[0]}\n${max[1].join(' ')}`;
    console.log(answer);

🧐 후기

이전에 풀었던 문제의 응용이었다.
N = 1일 때와, 가장 긴 부분을 출력하는 부분 때문에 몇차례 실패 했지만, 생각보다 바로바로 반례가 생각나서 금방 수정할 수 있었다.