[Silver III] 현대모비스 부품 조립 - 34225

문제 링크

성능 요약

메모리: 176604 KB, 시간: 704 ms

분류

그리디 알고리즘, 정렬

제출 일자

2025년 11월 11일 19:21:49

문제 설명

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

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

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

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

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

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

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

입력

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

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

출력

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

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

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

---

💡 해결 방법

💻 코드

# https://www.acmicpc.net/problem/34225
 
import collections
from collections import deque
import itertools
import sys
input = sys.stdin.readline
 
 
    
 
 
n = int(input())
a_scores_ori = (list(map(int, input().split())))
 
for i in range(len(a_scores_ori)):
    a_scores_ori[i] = [a_scores_ori[i], i + 1]
 
a = sorted(a_scores_ori, reverse= True)
 
# print(a)
 
now = [[a[0][0] + a[0][0] + a[0][0], 0]]
# print(now[-1][0])
 
 
 
 
for i in range(1, len(a)):
        
        now.append(
            [now[-1][0] - a[i - 1][0] + a[i][0] + a[i][0], i]
            )
 
        
        
    
 
 
 
ans = max(now)
 
# print(ans[0])
# print(ans)
 
# print(a)
# print(ans[1])
 
print(ans[1] + 1)
 
for i in range(0, ans[1] + 1):
    print(a[i][1], end = ' ')