안녕하세요,
재재입니다.
BOJ 1209 단조수열 만들기 문제 풀이입니다.
BOJ 1209 단조수열 만들기
(1) 문제 설명
분류 : dynamic programming
출처 : https://www.acmicpc.net/problem/1209
(2,000 이하) N개의 숫자가 주어집니다.
이 수열에 적절히 숫자를 더해서,
단조 증가 혹은 단조 감소의 수열을 만들어야 합니다.
이때, 더해진 숫자의 합의 최솟값을 구해주면 됩니다.
(2) 풀이 도출
가장 효과적인 방법은,
주어진 N 개의 수열을 정렬하여 오름차순 및 내림차순 (단조) 으로 만드는 것입니다.
이제 상태공간을 정의하면 다음과 같습니다.
dp[i][j] : 현재 i번째 값이고 정렬한 상태의 j 번째 값인 상태일 때,
남은 수열을 단조 수열로 만드는 데 드는 비용의 최솟값
모든 숫자를 사용할 필요는 없고,
필요에 의해 적절히 선택지를 가져갈 수 있습니다.
이때, 시간복잡도는 $$ O(n^2) $$ 입니다.
(3) 정답 코드
BOJ 1209 단조수열 만들기