Informatica Online Judge

  양동이 개수 [2311 / 0907]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 20   Total Tried : 20


The Champion of this Problem (C++) : gs17004 - ms / 299byte
My Best Submission (C++) : N/A

[USACO2018DecBronze]

Background

농부 존은 젖소 우유를 짜는데 사용할 양동이들을 어떻게 배치할지 고민하고 있다. 어떻게 하면 양동이들을 최소 개수로 사용할 수 있는지 고민 중인데 어떻게 해야할지 잘 모르겠다.

존에게 N마리의 젖소가 있고 각각의 젖소를 1...N 번이라고 하자.

i번째 젖소는 si 시간부터 ti시간까지 우유를 짜야하고 bi 개의 양동이가 필요하다.

여러 젖소의 우유를 동시에 짤 수 있고, 동시에 끝날 수 있다.; 하지만, 그런 경우 서로 다른 양동이를 사용해야한다. 그렇기 때문에, 어떤 젖소의 젖을 짜는 si 시간부터 ti 시간까지는 그 젖소에게 할당된 양동이만 사용할 수 있다. 어떤 젖소가 양동이를 사용하지 않고 있어야 다른 젖소가 그 양동이를 사용할 수 있기 때문이다.

농부 존은 일을 간단하게 하기 위해 우유를 짜기 시작하는 시간과 끝내는 시간이 모두 겹치지 않게 다르게 하였다.

농부 존에게는 우유 양동이를 보관하는 저장실이 있고, 저장실에는 순서대로 1, 2, 3 ... 번호가 붙여진 양동이들이 있다. 농부 존이 생각한 우유짜기 계획에서, 어떤 i번 젖소에서 si 시간부터 우유를 짜기 시작하면, 존은 저장실에가서 사용할 수 있는 가장 작은 번호의 양동이부터 bi 개의 양동이를 가져와서 i번 젖소의 우유짜기에 사용한다.

모든 젖소의 우유를 짜기 위해서 농부 존이 저장소에 가지고 있어야 하는 최소 양동이의 개수를 알아보자.

Input

첫 번째 줄에 젖소의 마릿수(N)가 입력된다.
두 번째 줄부터 N개의 줄에는 각 젖소의 우유짜기를 시작하는 시간(si)과 끝내는 시간(ti), 필요한 양동이 개수(bi)가 공백을 두고 순서대로 입력된다.

1<= N <=100
1<= si,ti <= 1000
1<= bi <=10

Output

필요한 양동이의 최소 개수를 출력한다.

IO Example

입력예시
3
4 10 1
8 13 3
2 6 2

출력예시
4

설명
양동이 4개면 충분하다.:
1번 양동이와 2번 양동이를 세 번째 젖소(시작시간 2) 우유짜기에 사용한다.
첫 번째 젖소(시작시간 4)에는 3번 양동이를 사용하고, 두 번째 젖소 우유짜기를 시작시간 8에 시작할 때에는 1번 양동이와 2번 양동이를 사용할 수 있는데 양동이가 1개 더 필요하기 때문에 1, 2, 4 번 양동이를 사용해야한다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]