루미 알고리즘

#1233브론즈두사와 요비들Dusa And The Yobis

CCC 2024코딩주니어 2번영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문을 루미 알고리즘이 한국어로 옮겼습니다. 뜻이 다르면 원문이 맞습니다. (검수일 2026-11-19)

두사와 요비들

원제: Dusa And The Yobis

문제

두사(Dusa)는 요비(Yobi)를 먹습니다. 하지만 특정한 크기의 요비만 먹습니다.

두사가 자기보다 작은 요비를 만나면, 두사는 그 요비를 먹고 요비의 크기를 흡수합니다. 예를 들어 크기가 10인 두사가 크기가 6인 요비를 만나면, 두사는 그 요비를 먹고 크기가 10 + 6 = 16 으로 커집니다.

두사가 자기와 크기가 같거나 자기보다 큰 요비를 만나면, 두사는 그 요비를 먹지 않고 도망칩니다.

지금 두사 앞에는 요비들이 한 줄로 서 있고, 두사는 요비들을 순서대로 만납니다. 두사는 언젠가 반드시 자신을 도망치게 만드는 요비를 만납니다. 그때 두사의 크기를 구하세요.

원문 탭의 그림을 참고하세요.

입력

첫째 줄에 두사의 처음 크기를 나타내는 양의 정수 D가 주어집니다.

나머지 줄에는 요비들의 크기를 나타내는 양의 정수들이 순서대로 주어집니다.

출력

두사가 마침내 도망칠 때의 크기인 양의 정수 R을 출력합니다.

예제

예제 1

입력
5
3
2
9
20
22
14
출력
19

두사는 크기가 3인 요비를 먹을 수 있을 만큼 큽니다. 그래서 두사의 크기는 8이 됩니다. 두사는 크기가 2인 요비를 먹을 수 있을 만큼 큽니다. 그래서 두사의 크기는 10이 됩니다. 두사는 크기가 9인 요비를 먹을 수 있을 만큼 큽니다. 그래서 두사의 크기는 19가 됩니다. 크기가 20인 요비를 만나면 두사는 도망칩니다.

예제 2

입력
10
10
3
5
13
출력
10

크기가 10인 요비를 만나면 두사는 도망치고, 두사의 크기는 그대로입니다.

채점 데이터와 풀이는 그 해 문제 전체가 한 묶음입니다. 받으면 이 문제의 것만이 아니라 2024년 대회 전체가 들어 있습니다.

자료

출처 표기

출처: Centre for Education in Mathematics and Computing (CEMC), University of Waterloo 2024년 · 원문 페이지 · 이용 조건 CC BY-NC 4.0 · 부문별 문제지 한 권에서 해당 문제 부분을 보여 줍니다. 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-비영리 4.0 국제. 비영리 목적으로만 이용할 수 있습니다.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.