Boj 12864 c++ 사서왕 준서

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

 

문제

 

책의 번호가 나열된 길이 n의 실수 수열과 각 책을 옮기는데에 드는 비용이 주어진다.

나열된 책들을 번호가 오름차순이 되도록 책을 옮길 때, 최소 비용을 구해야한다.

(1<= n <= 5000)

 

 

접근

책을 옮기는 위치에 관계 없이 항상 옮기는 비용이 일정하다면, 최대한 비용이 작은 책들을 옮기는 것이 좋을 것이다.

이를 반대로 생각하면 우리는 비용의 합이 가장 큰 증가하는 부분수열을 구한 후, 전체 비용합에서 이를 제외해주면

책을 정렬하는데 드는 최소 비용을 구할 수 있을 것이다.

 

 

 

전체코드

 

 

#include <bits/stdc++.h>
using namespace std;
int dp[5050], cost[5050], ans, sum, N;
double arr[5050];

int main() {
	
	cin >> N;
	
	for(int i = 1; i <= N; i++) {
		cin >> arr[i];
	}
	for(int i = 1; i <= N; i++) {
		cin >> cost[i];
		sum += cost[i];
	}
	for(int i = 1; i <= N; i++) {
		dp[i] = cost[i];
		for(int j = 1; j <= i-1; j++) {
			if(arr[j] <= arr[i]) {
				dp[i] = max(dp[i], cost[i] + dp[j]);
			}
		}
		ans = max(dp[i], ans);
	}
	cout << sum - ans;
}

 

 

이런식으로 발상의 전환이 필요한 문제도 많이 풀어봐야겠다.