[고등부] 2025 KOI 1차대회 대비 모의고사 (5주차)

정올 베이커리는 자동 반죽 기계를 이용해 손님이 요청하는 크기의 빵을 직접 구워주는 시연회를 준비하고 있다.
각 반죽 기계는 설정된 반죽 크기만큼 정확히 반죽하여 빵을 구운다.

새로운 반죽 기계의 초기 반죽 크기 설정값은 1이다.
그리고 기계는 시연 중에 원할 때마다 설정값을 더 큰 값으로 조정할 수 있지만, 절대로 줄일 수는 없다.

시연회는 총 N명의 손님이 차례로 방문하며, 각 손님은 원하는 빵의 크기 Aᵢ를 요청한다.
각 요청에 대해 베이커리는 다음 세 가지 중 하나를 선택할 수 있다:

1. 기존 기계 하나의 반죽 크기 설정값을 Aᵢ로 올려서 빵을 구워준다.

   • 이 경우, 반죽 크기 설정은 늘릴 수는 있지만 줄일 수 없기에 해당 기계의 현재 설정값이 Aᵢ 이하여야 한다.

2. 새로운 기계를 추가로 구입하고, 그 기계의 설정값을 Aᵢ로 설정하여 빵을 구워준다.

3. 요청을 거절한다.

   • 단, 두 번 연속으로 요청을 거절하면 손님들이 화를 내고 시연회는 실패하게 된다.

정올 베이커리의 시연회를 당담하게 된 당신은 N명의 손님 요청 A₁, A₂, ..., A_N이 주어졌을 때,
시연회를 실패시키지 않으면서 사용해야 하는 반죽 기계의 최소 개수를 구해야 한다.