[BOJ] 17216 - 가장 큰 감소 부분 수열 (Python, JavaScript)

 

 

아이디어

 

동적 계획법으로 감소하는 수열 합의 최댓값을 구한다.

 

 

풀이 #1 (Python)

 

리스트 dp에 수열 A와 같은 값들을 저장한다.

이중 for문에서 수열의 두 요소를 비교하여 수가 감소할 때 더 큰 부분 수열의 합으로 갱신해 나간다.

max(dp)로 전체 감소 부분 수열의 합 중 가장 큰 값을 찾아 출력한다.

 

def solution():
    N = int(input())
    A = tuple(map(int, input().split()))
    dp = list(A)
    for i in range(N):
        for j in range(i+1, N):
            if A[j] < A[i] and dp[i]+A[j] > dp[j]:
                dp[j] = dp[i]+A[j]
    print(max(dp))

solution()

 

 

 

풀이 #2 (JavaScript)

 

풀이 #1과 마찬가지 방식으로 동작하며, 스프레드 연산자를 이용하여 A의 값들을 배열 dp에 복사한다.

 

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

const N = +input[0];
const A = input[1].split(' ').map(Number);
let dp = [...A];
for (let i=0; i<N; i++) {
    for (let j=i+1; j<N; j++) {
        if (A[j] < A[i] && dp[i]+A[j] > dp[j]) dp[j] = dp[i]+A[j];
    }
}
console.log(Math.max(...dp));