[백준 28359] 수열의 가치 [Java]

문제

http://boj.ma/28359

28359번: 수열의 가치

 

---

풀이

문제 요약

주어진 수열이 증가하지 않는 부분 수열(P), 감소하지 않는 부분 수열(C)가 되도록 재배열하여 주어진 규칙대로 수열의 가치가 최댓값을 가지도록 하자.

아이디어

예제의 경우 P = {1, 2, 2}, Q = {3, 2, 2} 로 구성되며, {2, 2}가 중복되어 최대 가치 12를 가진다.

수열의 가치에 중복 계산하는 수를 제외한다면, 수열을 재배열 할 때 P 또는 Q는 1개의 요소로도 충분하므로 정렬을 수행할 수 있다.

P 또는 Q는 부분 수열이므로, 중복 계산되는 수를 포함하는 것으로 충분하다.

중복 계산되는 수는 빈도와 값의 곱이 큰 수로 결정해주자.

        // Solve
        Arrays.sort(A);
        Map<Integer, Integer> freq = new HashMap<>();
        for (int a : A) {
            freq.put(a, freq.getOrDefault(a, 0) + 1);
        }
        int maxFreqValue = 0;
        for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
            final int val = e.getKey();
            final int count = e.getValue();
            maxFreqValue = Math.max(maxFreqValue, val * count);
        }
        
        // Output
        sb.append(Arrays.stream(A).sum() + maxFreqValue).append("\\n");
}

아이디어

20분

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/normal/28359.java

problem-solving/baekjoon-online-judge/normal/28359.java at main · rogi-rogi/problem-solving