[JS][백준]17216_가장 큰 감소 부분 수열

문제 번호

17216번: 가장 큰 감소 부분 수열

 

 

 

알고리즘 분류

• 다이나믹 프로그래밍

 

문제 풀이

 많이 등장하는 DP 알고리즘 문제이다. 가장 큰 증가, 감소, 이어지는, 가장 긴 등등 여러가지 형태로 바뀌어서 많이 나오는걸 봤었다. 

 

 문제에서 주어지는 수열을 내용을 모두 검사한다. DP[i]는 i 번째 인덱스를 마지막으로 하는 감소하는 부분수열중 합이 가장 클때의 값이다. DP[3] = 89라면 인덱스 3의 내용을 마지막으로 하는 감소 부분 수열들 중에 합이 가장 클때의 값이 89라는 뜻이다.

 

 이를 바탕으로 이중 for문 구조를 사용하여 문제에서 주어진 수열을 처음부터 끝까지 탐색할 것이다. j는 자신보다 낮은 인덱스의 수들을 살펴보면서 자신보다 큰 수 인지 확인한다. 만약 자신보다 큰 수 라면 이때의 DP값을 확인해본다. 우리는 가장 큰 합을 구하는것이 목표이기 때문에 i보다 작은 인덱스들을 살펴보며 i인덱스의 수보다 큰 수(arry값)를 갖는지 살펴본다. 그리고 큰 수를 갖는 인덱스들 중, 합이 가장 큰 수에 j 번째 수를 더해주면 DP[j]를 구할 수 있다. 

 

 1. ) 감소하는 부분 수열이여야한다.

 2. ) 그들 중 합이 가장 켜야한다. (여기에 arry[j]를 더해주면 가장 큰 감소 부분 수열이다.)

그러면 두 조건을 모두 만족한다.

 

전체코드

function sol(arry) {
  let dp = new Array(arry.length + 1);  // dp[i] : i를 마지막으로 갖는 감소 수열중 합이 가장 클때의 값.  

  let answer = 0;
  for (let i = 0; i < arry.length; i++) {
    let maxSum = 0;
    for (let j = 0; j < i; j++) {
      if (arry[i] < arry[j]) {  // 현재보다 큰가?
        if (maxSum < dp[j]) { // 합도 큰가?
          maxSum = dp[j];
        }
      }      
    }
    dp[i] = maxSum + arry[i];
    if (dp[i] > answer) {
      answer = dp[i];
    }
  }
  console.log(answer);
}

function insert() {
  const input = require('fs').readFileSync('가장 큰 감소 부분 수열/input.txt').toString().trim().split('\n');
  const n = +input[0];
  const arry = input[1].split(' ').map(Number);
  sol(arry);
}
insert();

특이사항

 처음에 개념을 잡기가 어려웠지만 한번 이해하고 나면 여러가지 방법으로 응용이 가능한 문제였다. 까먹지 않도록 자주 봐야겠다.