BOJ : 1965 상자넣기 (JS)

소스코드

let fs = require('fs');
const filePath = process.platform === `linux` ? `/dev/stdin` : `예제.txt`; 
let input = fs.readFileSync(filePath).toString().split('\n');
const c = console.log

n= Number(input[0])

let numbers = input[1].split(" ").map(Number)

let dp = []

for(let i = 0 ; i < n ; i++){
    dp[i] = 1
} 

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

    }
}
c(Math.max(...dp))

 

풀이

박스안에 작은 박스를 계속해서 넣는 다이나믹 프로그래밍 방식의 문제이다.

 

입력1

 

값	1	6	2	5	7	3	5	6
dp	1	2	2	3	4	3	4	5

7인경우 1257 로 4개를 넣을 수 있다. 라는 부분이 좀 헷갈렸습니다.

 

문제

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

1965번: 상자넣기