34096번 - 자동 광고 배치 시스템 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 83 | 47 | 38 | 60.317% |
문제
Moloco는 전 세계의 다양한 회사들이 온라인 광고를 더 잘할 수 있도록 돕는 광고 기술 회사이다. Moloco의 기술을 사용하면 인터넷 사용자들이 더 관련성 높은 광고를 볼 수 있게 되고, 광고주들은 효과적으로 광고를 할 수 있다.
Moloco의 자동 광고 배치 시스템은 대기 중인 광고 요청들을 실시간으로 묶어 처리하여 효율을 최적화한다. 각 광고 요청에는 그 요청을 처리할 때의 비용을 나타내는 양의 정수 값이 정해져 있다. 총 $N$개의 광고 요청이 순서대로 대기열에 주어졌을 때, 시스템은 다음 과정을 반복하여 모든 요청을 소화한다.
- 현재 대기열의 앞쪽에서 최대 3개의 광고 요청을 확인한 다음, 그 중 2개의 요청을 선택하여 동시에 처리하고 제거한다. 이때 발생하는 비용은 선택된 두 요청 중 작지 않은 값이다.
- 만약 대기열에 단 하나의 요청만 남아 있다면, 그 요청을 단독 처리하고 제거한다. 이때의 비용은 그 요청의 값이 된다.
시스템이 모든 광고 요청을 처리하기 위해 필요한 총 비용의 최솟값을 구하시오.
입력
첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. ($1\le T\le 50\, 000$)
각 테스트 케이스의 첫째 줄에는 광고 요청의 개수 $N$이 주어진다. ($1\le N\le 1\, 000\, 000$)
각 테스트 케이스의 둘째 줄에는 각 광고 요청의 비용을 의미하는 $N$개의 정수 $A_1,A_2,\cdots ,A_N$이 공백으로 구분되어 주어진다. ($1\le A_i\le 10^9$)
모든 테스트 케이스에 대해 $N$의 합은 $1\, 000\, 000$ 이하이다.
출력
각 테스트 케이스에 대해 모든 광고 요청을 처리하기 위해 필요한 총 비용의 최솟값을 $T$개의 줄에 걸쳐 순서대로 출력한다.
예제 입력 1
2 5 1 6 3 2 5 2 314 1592
예제 출력 1
11 1592
출처
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호