백준 11053 JavaScript

문제

백준 11053

풀이

이 문제는 Dynamic Programming으로 풀이한다.
우선 증가하는 수열이 되어야 하는 조건이 있다.
주어진 배열(여기선 A)을 순회하면서 그 전에 위치한 수와 크기를 비교한다.

현재 순회하고 있는 값(i)의 전 단계(i-1)에 증가하는 수열의 길이를 DP[i-1]에 저장해놨으므로 현재 값이 크다면 거기에 1을 더해주면 된다.

기본적으로 자기 자신을 포함할테니 DP 배열의 값은 모두 1로 초기화한다.

• 10(A[0])과 비교할 때, DP[0], DP[3] 모두 1이다. DP[3]에 1을 더한 2를 할당한다. ➡️ DP[3] = 2
• 20(A[1])과 비교할 때, 20보다 작은 수로 만들어진 수열의 길이는 2(DP[1]) 여기에 1을 더하면 3이 된다. 기존 DP[3]의 값보다 크므로 교체한다. ➡️ DP[3] = 3

• 10(A[0])과 비교할 때, DP[0]과 DP[5]는 모두 1이다. DP[5]에 1을 더한 2를 할당한다.➡️ DP[5] = 2
• 20(A[1])과 비교할 때, DP[1]과 DP[5]는 모두 2다. DP[5]에 1을 더한 3을 할당한다. ➡️ DP[5] = 3
• 30(A[3])과 비교할 때, DP[3]과 DP[5]는 모두 3이다. DP[5]에 1을 더한 5를 할당한다. ➡️ DP[5] = 4

코드

가장 긴 수열을 구해야 하므로 만들어진 DP 배열에서 최댓값을 출력하면 된다.

const readFileSyncPath = '/dev/stdin';
const input = require('fs').readFileSync(readFileSyncPath).toString().split("\n");
const N = Number(input.splice(0, 1));
const A = input[0].split(" ").map(Number);
const DP = new Array(N).fill(1);

for (let i = 0; i < N; i++) {
  let currVal = A[i];      // 현재 값
  for (j = 0; j < i; j++) {
    if (currVal > A[j]) {  // 현재 값이 순회하는 값보다 크면
      DP[i] = Math.max(DP[i], DP[j] + 1); // DP[j]에 만들어진 수열 길이와 현재(i) 길이 비교 
    }
  }
}

// 최댓값 
console.log(Math.max(...DP));

되돌아보기

처음 나의 풀이는 🐶떡같았다. DP를 사용해야하는 것을 알면서도 배열만 DP라는 것을 선언해놓고 이용하지를 않았다. 그래서 이전 값과 비교만 하다가 반복문이 끝났다. DP에 대한 더 많은 문제 풀이가 필요하다...

reference

• https://bitwise.tistory.com/215