[ 백준 28359 ] 수열의 가치 (c/c++)

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

 

 

[ 문제 요약 ]

최대 N개의 숫자가 주어질 때, 이 수들을 배열하여서 감소하지 않는 부분 수열과 증가하지 않는 부분 수열의 합의 최댓값과 그러한 최대값을 가지는 수열을 출력한다.

 

 

[ 문제 풀이 ]

1. 증가하지 않는 부분 수열의 값이 커지게 되는 수열을 만들게 되면 감소하지 않는 부분 수열이 그만큼 줄어들게 되고 감소하지 않는 부분 수열의 값이 커지게 되면 증가하지 않는 부분 수열의 값이 그만큼 감소하게 된다.

2. 즉, 오름차순으로 정렬하여 감소하지 않는 부분 수열의 값을 가장 크게 만든다.

3. 정렬한 뒤에 증가하지 않는 부분 수열의 값은 특정한 수 * 그 수가 나온 횟수가 가장 큰 값이 된다.

 

 

[ 소스 코드 ]

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

int N, sum = 0, temp = 0;
int arr[1010];
map<int, int> m;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    for (int i=0; i<N; i++){
        cin >> arr[i];
        m[arr[i]]++;
        sum = sum + arr[i];
        temp = max(temp, m[arr[i]] * arr[i]);
    }

    sort(arr, arr+N);

    cout << sum + temp << "\n";
    for (int i=0; i<N; i++){
        cout << arr[i] << " ";
    }
    
    return 0;
}

 

 

[ 문제 풀이 ]

map을 이용해서 특정한 수가 나올 때마다 횟수를 체크하게 되면 증가하지 않는 부분 수열의 합을 쉽게 구할 수 있다.