백준 34225 (C++) 현대모비스 부품 조립

최초 업로드: 2025-09-02 16:50:49

최근 수정 시간: 2025-09-02 16:51:13

게시자: rlatjwls3333

카테고리: 백준

# [Silver IV] 현대모비스 부품 조립

[문제 링크](https://www.acmicpc.net/problem/34225)

## 문제 설명

<blockquote>현대모비스에선 최적의 모듈 개발로 자동차 업체의 플랫폼 및 부품 공용화를 위한 핵심기술을 연구하고 있어 생산성 향상 및 품질 향상을 극대화합니다.</blockquote>

자동차 조립 전문가인 당신은 $N$개의 차량 모듈을 가지고 있다. $i$번째 모듈은 $A_i$만큼의 효율성을 가진다.

당신은 $1$개 이상의 모듈을 골라 조립해 자동차를 만들어야 한다. 이때, 하나의 모듈을 두 번 이상 고를 수는 없다. 당신이 조립한 자동차는 세 명의 연구원 숭돌이, 고돌이, 한돌이에게 철저한 심사를 받는다.

구체적으로, 각 연구원은 다음과 같은 기준으로 자동차의 점수를 매긴다.

<ul>
	<li>숭돌이는 자동차에서 효율성이 가장 낮은 차량 모듈의 효율성만큼 점수를 준다.</li>
	<li>고돌이는 자동차에서 효율성이 가장 높은 차량 모듈의 효율성만큼 점수를 준다.</li>
	<li>한돌이는 자동차에 사용된 모든 차량 모듈의 효율성의 합만큼 점수를 준다.</li>
</ul>

자동차의 점수는 세 연구원이 자동차에 매긴 점수를 모두 합한 값이다.

모든 차량 모듈의 효율성이 주어졌을 때, 어떻게 자동차를 조립해야 최고 점수를 받을 수 있는지 구하여라.

## 입력

첫째 줄에 차량 모듈의 개수 $N$이 주어진다. $(1 \leq N \leq 200\,000)$

둘째 줄에 각 차량 모듈의 효율성을 나타내는 정수 $A_1, A_2, ..., A_N$이 공백으로 구분되어 주어진다. $(1 \leq A_i \leq 10^9)$

## 출력

첫째 줄에 최고 점수를 받는 자동차에 들어가는 차량 모듈의 개수를 출력한다.

둘째 줄에 자동차에 들어가는 차량 모듈의 번호를 아무 순서로 공백으로 구분하여 출력한다.

가능한 답이 여러 가지라면, 그중 아무것이나 출력한다.

## 풀이
어떤 수를 선택했을 때, 그것보다 크거나 같은 수는 전부 선택하는 것이 최선입니다. 내림차순으로 정렬해서 어디까지 선택해야할지 정하면 됩니다.

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

typedef long long ll;

struct element {
 ll val, idx;
 bool operator<(const element e) const {
 return val > e.val;
 }
};

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int n; cin >> n;
 vector<element> v(n);
 for(int i=0;i<n;i++) {
 cin >> v[i].val;
 v[i].idx = i+1;
 }
 sort(v.begin(), v.end());

ll r=1, maxVal=v[0].val*3, preSum=v[0].val;
 for(int i=1;i<n;i++) {
 preSum += v[i].val;
 if(maxVal < v[0].val+v[i].val+preSum) {
 maxVal = v[0].val+v[i].val+preSum;
 r=i+1;
 }
 }

cout << r << '\n';
 for(int i=0;i<r;i++) cout << v[i].idx << ' ';
}
```