영어 원문을 루미 알고리즘이 한국어로 옮겼습니다. 뜻이 다르면 원문이 맞습니다. (검수일 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인 요비를 만나면 두사는 도망치고, 두사의 크기는 그대로입니다.