백준 js 1965번

<백준 문제>

 

- 알고리즘 분류 : 다이나믹 프로그래밍 -

https://www.acmicpc.net/problem/1965

1965번: 상자넣기

 

 

 

📕문제 핵심

✔️ 첫 항의 값은 무조건 1이다.

✔️ 각 위치에서의 최대 상자 갯수를 지정하는 배열을 만들어야 한다.

 -> 현재 위치에서 이 전 요소들을 모두 비교하기에 시간복잡도는 O(n^2) 이다.

 -> 밑에 순서도에서 4번, 5번이 이 문제의 핵심이다.

 

 

📕문제 해결방법 및 순서도

 

    1. 상자의 갯수 n을 가져온다.(n=8)

 

    2. 상자의 크기가 나열되어 있는 배열을 생성한다.(boxes)

 

    3. 2번에서 만든 배열을 인자로 하여 함수를 호출한다.

 

    4. 배열의 갯수만큼 각 위치에서의 최대 상자 갯수를 지정하는 배열을 만들고 1로 초기화 한다.

        ex. [1, 1, 1, 1, 1, 1, 1, 1,]

 

    5. 2중 반복문을 사용하여 각 상자에 대해서 이전의 모든 상자들을 확인한다. ✨

    -> i를 기준으로 전 요소들에 대해 확인한다.

    -> 전 요소들을 가리키는 j번째 값이 i번째 값보다 작다면 i번째 항을 j번째 항에 이어붙일 수 있다.

        <예를 들어, 상자 크기가 [1, 3, 2]인 경우>    

         i=2 (상자 크기 2)일 때, j=0 (상자 크기 1)에 대해 boxes[j] < boxes[i] 조건이 만족한다.

         이때, dp[0]은 1이므로(첫번째 항은 무조건 1), 상자 1 다음에 상자 2를 넣을 수 있기 때문에

         dp[2]의 값을 dp[0] + 1 ( = dp[j] + 1 ) 즉, 2로 갱신할 수 있다.

 

         <일부 코드 발췌>

for (let i = 1; i < n; i++) {

    for (let j = 0; j < i; j++) {

      if (boxes[j] < boxes[i]) {

        dp[i] = Math.max(dp[i], dp[j] + 1);

      }

    }

  }

  

    6. 모든 상자를 검토했을 때 4번 배열에서 가장 큰 값을 return 한다.

 

    7. return 된 변수를 출력한다.

 

 

 

- 구현 코드

 

const input = require("fs")

  .readFileSync(0, "utf-8")

  .toString()

  .trim()

  .split("\n");

// 첫 번째 입력 줄에서 상자의 수 가져오기

const n = parseInt(input[0]);

// 두 번째 입력 줄에서 상자의 크기 배열을 가져오기

const boxes = input[1].split(" ").map(Number);

function longestIncreasingSubsequence(boxes) {

  const n = boxes.length;

  const dp = new Array(n).fill(1); // 모든 상자에 대해 최대 길이는 처음에 1로 초기화

  for (let i = 1; i < n; i++) {

    for (let j = 0; j < i; j++) {

      if (boxes[j] < boxes[i]) {

        dp[i] = Math.max(dp[i], dp[j] + 1);

      }

    }

  }

  return Math.max(...dp); // dp 배열에서 최대값 찾기

}

// 함수를 호출하고 return값 출력

const result = longestIncreasingSubsequence(boxes);

console.log(result);