USACO 2023 February Contest, Bronze Problem 1 Hungry Cow

USACO 2023 February Contest, Bronze 1번 문제 Hungry Cow 입니다.

본 포스트는 이해를 돕기 위해 문제를 간략하게만 정리하였으므로 상세 내용과 코드 제출은 아래 링크를 참고해 주세요.

USACO

 

문제 개요 설명

---

배고픈 소 베시는 매일 저녁에 저녁 식사로 건초 한 덩이를 먹습니다.

농부 존은 이런 베시를 위해 특정한 날 아침에 베시에게 건초를 배달해 줍니다. 건초는 항상 그날 베시의 식사 시간 전에 도착합니다.

총 T일 중에서 존이 건초를 배달하는 특정 날짜 d_i들과 그날 배달하는 건초의 개수 b_i들이 주어질 때, T일동안 베시는 몇 개의 건초를 먹게 될지 계산해 주세요.

 

입력

---

• 첫 번째 줄에는 N과 T가 포함됩니다. (1 ≤ N ≤ 10⁵, 1 ≤ T ≤ 10¹⁴).
• 다음 N줄에는 건초 배달 날짜 d_i과 그날 배달되는 건초의 개수 b_i가 주어집니다. (1 ≤ d₁ < d₂ < ⋯ < d_N ≤ T.)

 

출력

---

• T일 동안 베시가 먹게 되는 건초의 개수를 출력합니다.

 

입출력 예시

---

입력 :

2 5
1 2
5 10

출력 :

3

5일 동안 베시가 먹은 건초의 수를 구하는 예시입니다.

존이 베시에게 건초를 배달한 횟수는 총 2회로, 1일 5일 두 번입니다. 1일에는 2개의 건초를, 5일에는 10개의 건초를 배달하였습니다.

이에 따라 베시가 건초를 먹은 횟수는 다음과 같이 계산되어 정답은 3회입니다.

 

날짜	먹을 수 있는 건초의 수	베시의 저녁식사 여부
1일	2개	O
2일	1개	O
3일	0개	X
4일	0개	X
5일	10개	O

 

솔루션 코드

---

# 입력 처리하기
N, T = list(map(int,input().split()))
haybales = 0
days = []
delivery = []

for _ in range(N):
    day, count = list(map(int,input().split()))

    days.append(day)
    delivery.append(count)

# main
days.append(T+1)
delivery.append(0)

result = 0
for i in range(N):
    haybales += delivery[i]
    if days[i+1] - days[i] < haybales:
        result += days[i+1] - days[i]
        haybales -= days[i+1] - days[i]
    else:
        result += haybales
        haybales = 0
    
print(result)

건초가 배달되는 날짜와 그 다음번에 배달되는 날짜의 텀이 현재 보유하고 있는 건초의 수보다 작거나 같다면, 베시는 그 기간 동안에 매일 건초를 먹을 수 있습니다. 반대로 그렇지 않다면, 건초가 부족하여 굶는 날이 생길 수 있습니다.

이를 참고하여 베시가 건초를 먹는 데 있어서 어떤 규칙이 필요한지 생각해 봅시다!