[JavaScript] 백준 DP 문제 : 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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

입출력 예

입력	출력
6 10 20 10 30 20 50	4

• 처음에는 문제가 잘 이해되지 않았다
• 배열 [10, 20, 10, 30, 20, 50] 으로 만들 수 있는 부분 배열 중, 숫자가 연속적으로 커지는 배열의 최대 길이를 구한다
• 예를 들어, [10], [10, 20], [10, 20, 30] 은 연속적으로 숫자가 커지는 배열이지만,[10, 20, 10], [10, 30, 20] 은 연속적으로 커지지 않기 때문에 답이 될 수 없다
• 위의 입출력 예시에서는 [10, 20, 30, 50] 배열이 연속적으로 이어지는 부분 배열 중 길이가 가장 긴 배열이라 답이 4가 된다

 

첫번째 시도 - 문제 이해를 잘못함

처음에는 배열 내 앞의 숫자보다 커지는 수의 개수를 말하는 줄 알고 코드를 잘못 작성하였다. 당연히 오답 !

 

두번째 시도 - 여전히 문제 이해를 잘못함

이번에는 배열 내 앞의 숫자보다 커지는 수를 새로운 배열로 생각 했을 때, 그 배열의 최대 길이인 줄 알고 아래 코드를 작성했다.

function solution(A) {
    let n = +A[0]
    let nums = A[1].split(' ').map(Number);
    let maxLength = 0;

    for(let i = 1; i < n; i++){
        let cnt = 1;
        let increaseSet = new Set();
        for(let j = 0; j < i; j++){
            if(nums[j] < nums[i]) {
                if(!increaseSet.has(nums[j])){
                    increaseSet.add(nums[j]);
                    cnt++;
                }
            }
        }
        if(cnt > maxLength) maxLength = cnt;
    }

    console.log(maxLength);
}

당연히 오답 !

 

성공 코드

지피티의 도움으로 문제를 완전히 이해하고 dp를 적용시켜 문제를 풀어보았다.

1. '연속적'으로 증가하는 부분 배열을 구하기 위해, 이중 for문을 사용한다.
2. 첫번째 for문은 1번 인덱스부터 마지막 인덱스까지, 그 안의 두번째 for문은 0번째 인덱스부터 i-1번째 인덱스까지 돈다.
3. 모든 인덱스는 요소 1개(본인)를 가지고 있기에, 배열의 길이와 같은 배열을 생성하여 모든 값을 1로 채운다. → dp배열
4. for문에서 0부터 i-1까지 돌며 nums[i]보다 작은 값이 있으면 이 인덱스의 dp 값과 현재 dp 값을 비교하여 더 큰값을 할당한다.
   1. dp 배열은 모두 1로 채워져있고, 앞의 값부터 계산하게 된다.
   2. 예를 들어 i = 1, j = 0 일 때, nums[0]이 nums[1]보다 작은 값이라면 dp[1]에는 1 + 1인 2가 저장된다.
   3. 다음으로, i = 2, j = 1일 때, nums[1]이 nums[2]보다 작은 값이라면 dp[2]에는 dp[1] + 1인 3이 저장된다.
   4. 이 때 Math.max 함수를 사용하는 이유
      • nums[ j ]가 nums[ i ]보다 작은 값일 때, dp[ i ]에 값이 할당 되는데, 만약 i = 4라고 가정하자.
      • dp[2] = 3, dp[3] = 1 인 상태에서, nums[2], nums[3]이 nums[4] 보다 작은 값이라면 for문은 순차적으로 돌아 먼저 dp[4]는 dp[2]+1 = 4가 된다. 또 for문을 돌아 j가 3이 되었을 때, dp[3] = 1, dp[4] = 4이기에 이 때는 dp[4]가 4가 되어야한다.
      • 즉, 연속적으로 커지는 배열의 길이 중 최댓값을 구해야하기 때문에 Math.max 함수를 사용해야한다.
5. 따라서 본 문제의 핵심은 누적값 재사용이라는 것을 알 수 있다.

function solution(A) {
    let n = +A[0]
    let nums = A[1].split(' ').map(Number);
    let dp = Array(n).fill(1);

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

    let maxLength = Math.max(...dp);

    console.log(maxLength);
}

solution(A);

 

아직 혼자 생각해내기에는 어려움이 많은 것 같다. 공부를 더 해야겠다...🥲