30885번 - Φ² 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 1097 | 330 | 252 | 30.769% |
문제
선아는 최근에 어떤 미생물을 연구하고 있다. 선아는 연구 과정에서 이 미생물 여러 마리를 한 줄로 나열하면 미생물이 한 마리만 남을 때까지 다음 규칙들에 따라 미생물들이 서로 흡수한다는 사실을 알아냈다.
- 하루에 한 번 줄의 맨 앞에 있는 미생물부터 각 미생물은 차례대로 인접한 미생물 중 자신보다 크기가 작거나 같은 것들을 전부 흡수한다. 다른 미생물을 흡수한 경우, 미생물의 크기는 흡수한 미생물의 크기의 합만큼 커진다.
- 흡수당한 미생물은 사라지며 행동할 수 없다. 즉, $3$, $2$, $1$의 크기를 가지는 세 마리의 미생물들이 있는 경우 $2$는 자신의 차례가 오기 전에 $3$에게 흡수당하기 때문에 하루가 지난 후 남아있는 미생물들의 크기는 $5$, $1$이 된다.
- 흡수하는 미생물은 하루에 흡수할 모든 미생물을 한 번에 흡수한다. 즉, $3$, $4$, $5$의 크기를 가지는 세 마리의 미생물들이 있고 $4$의 차례인 경우 $4$는 $3$만 흡수한다. $4$가 $3$을 흡수해서 $7$이 된 후 같은 날 $5$를 흡수하는 행동은 불가능하다. 따라서 하루가 지난 후 남아있는 미생물들의 크기는 $7$, $5$가 된다.
선아에게는 이 미생물이 $N$마리 있다. 이 $N$마리의 미생물들이 한 줄로 나열되었을 때 마지막에 남는 미생물의 최종 크기와 초기 위치를 찾는 프로그램을 작성해 보자.
입력
첫 번째 줄에 미생물들의 수 $N$이 주어진다. $(1\le N\le 500\, 000)$
두 번째 줄에 미생물들의 초기 크기를 나타내는 $N$개의 정수 $a_1,a_2,\ldots ,a_N$가 공백으로 구분되어 주어진다. $a_i$는 $i$번째 미생물의 초기 크기를 나타낸다. 각 미생물의 초기 크기는 $1$ 이상 $N$ 이하의 정수이다. 또한 같은 초기 크기를 가지는 두 미생물은 존재하지 않는다.
출력
첫 번째 줄에 마지막에 남는 미생물의 최종 크기를 출력한다.
두 번째 줄에 그 미생물의 초기 위치를 출력한다.
예제 입력 1
5 4 1 3 2 5
예제 출력 1
15 5
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호