[BOJ 28359] 수열의 가치

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

28359번: 수열의 가치

 

- 문제 요약

 

어떤 정수 수열 X의 가치는 다음과 같이 정의된다:

•  X에서 감소하지 않는 부분 수열 P와 증가하지 않는 부분 수열 Q를 임의로 선택했을 때, (P의 모든 원소의 합) + (Q의 모든 원소의 합)의 최댓값

길이가 N인 정수 수열 A가 주어진다.

A를 원하는 대로 재배열하여 수열의 가치를 최대화하고 싶다.

재배열하여 만들 수 있는 수열의 가치의 최댓값과 이때의 수열을 찾아보자.

감소/증가하지 않는 부분 수열이 무엇인지 잘 모르는 친구들은 친절한 정휘가 준비한 아래 정의를 읽어보도록 하자.

• 부분 수열이란 주어진 수열에서 1개 이상의 원소를 골라 원래 순서대로 나열하여 얻은 수열을 말한다.
• 감소하지 않는 부분 수열은 맨 처음 원소를 제외한 모든 원소가 바로 이전 원소보다 크거나 같은 부분 수열을 말한다.
• 증가하지 않는 부분 수열은 맨 처음 원소를 제외한 모든 원소가 바로 이전 원소보다 작거나 같은 부분 수열을 말한다.

어떤 수가 두 부분 수열 P와 Q 모두에 포함되도록 P와 Q를 선택할 수 있으며, 둘 모두에 포함된 수는 P의 원소의 합을 구할 때와 Q의 원소의 합을 구할 때 모두 더해진다.

 

 

- 알고리즘 정리

 

P와 Q에 동시에 포함되는 원소를 최대한 많게 해야 수열의 가치를 최대화할 수 있습니다.

수열 A에 중복 원소가 없는 경우에는 P와 Q의 공통 원소가 최대 1개 존재할 수 있습니다.

중복 원소가 있는 경우에는 P와 Q의 공통 원소가 모두 같도록 해주고, 원소의 값 X 등장 횟수가 가장 큰 원소를 P와 Q에 두 번 등장시키면 최적해를 구할 수 있습니다.

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

#define MAX 1001
int n,arr[MAX],brr[MAX],crr[MAX];

int main(){
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
    cin>>n;
    for(int i=1;i<=n;i++){
    	cin>>arr[i];
	}
    sort(arr+1,arr+n+1);
    for(int i=1;i<=n;i++){
    	brr[i]=crr[i]=arr[i];
	}
    for(int i=1;i<=n;i++){
    	for(int j=1;j<i;j++){
    		if(arr[j]<=arr[i]){
    			brr[i]=max(brr[i],brr[j]+arr[i]);
			}
		}
	}
    for(int i=1;i<=n;i++){
    	for(int j=1;j<i;j++){
    		if(arr[j]>=arr[i]){
    			crr[i]=max(crr[i],crr[j]+arr[i]);
			}
		}
	}
    cout<<*max_element(brr+1,brr+n+1)+*max_element(crr+1,crr+n+1)<<'\n';
    for(int i=1;i<=n;i++){
    	cout<<arr[i]<<" ";
	}
}

코드 제출 결과