문제
정올 기상관측센터는 다음 날의 일기예보를 위해 구름을 덩어리 단위로 관측한다.
관측 결과, 관측한 지역에 동풍이 불고 있으며, 모든 구름이 왼쪽에서 오른쪽으로 이동하고 있음을 알아냈다.
구름은 각각 다른 크기를 가지고 있으며, 1부터 N까지의 좌표를 가진 수직선 상단에 제각기 다른 속도를 가지고 떠다닌다.
1, 2, 3,…N까지의 각 정수 좌표에는 도시들이 위치한다.
속도 vi를 가진 구름은 하루에 vi만큼 오른쪽으로 움직인다.
두 개의 구름은 한 도시 상공에서 만났다고 해서 서로 합쳐지지는 않고 다음 날 각자의 속도를 가지고 움직인다.
어느 날 어느 도시 상공에, 구름 크기의 총합이 100 이상이면, 그 도시 지역은 그 날 비가 온다.
예를 들어 N=7개의 도시가 있는 상태에서, 오늘 관측한 구름이 다음과 같이 위치해 있다고 하자.
구름 |  |
|  |  |
|
|
|
크기 | 40 |
| 50 | 70 |
|
|
|
도시 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
도시 1 상공에 위치한 구름의 속도가 3,
도시 3 상공의 구름 속도가 2,
도시 4 상공의 구름 속도가 1이라고 하자.
다음 날 오른쪽 두 구름이 도시 5 상공에서 만나 총 120의 구름량이 도시 5 위에 생긴다. 따라서 도시 5에 비가 오게 된다.
구름 |
|
|
|  |   |
|
|
크기 |
|
|
| 40 | 50+70 |
|
|
도시 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
그 다음 날 크기 40의 구름과, 크기 50의 구름이 도시 7 상공에서 만나 총 90의 구름량이 도시 7 상공에 생기지만, 총합이 100이 넘지 않으므로 이 날 도시 7엔 비가 내리지 않는다.
구름 |
|
|
|
|
|  |   |
크기 |
|
|
|
|
| 70 | 40+50 |
도시 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
오늘 하늘의 구름의 상태를 입력받아, 1번부터 N까지의 도시 중에, K일 뒤 비가 내리는 도시의 수를 출력하는 프로그램을 작성하라.
입력
첫 줄에 도시의 수인 N과 구름의 수인 M, 문제에서 제시한 K값이 공백을 사이에 두고 각각 주어진다.
둘째 줄부터 다음 M개의 줄에 걸쳐서, 오늘 관측된 구름의 현재 위치 pi와 크기 si, 속도 vi가 공백을 사이에 두고 주어진다. 같은 도시 상공에 다양한 속도를 가진 여러 개의 구름이 위치하고 있을 수 있다.
[부분문제의 제약 조건]
모든 부분문제에 있어서 1≤N≤100, 1≤M≤100, 0≤K≤100, 1≤pi≤N, 1≤si≤500, 1≤vi≤100을 만족하며, 이 조건에 맞춰 답을 낼 수 있다면 100점이다.
입력되는 모든 수는 양의 정수이다.
출력
첫 줄에 K일 뒤에 비가 오는 도시의 수를 출력한다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 10점 | N=100, M=100, K=10이며, 입력으로 주어지는 구름은 10일 뒤에 모두 한 곳에서 만난다. |
| #2 | 10점 | K=0이다. |
| #3 | 20점 | 모든 구름의 속도 vi가 일정한 값으로 같으며, K일 뒤에 도시 지역을 벗어나는 구름은 없다. |
| #4 | 30점 | 구름의 현재 위치 pi가 일정한 장소로 모두 같다. |
| #5 | 30점 | 주어진 제약 외에 추가 제약이 없다. |
예제 #1
7 3 0
1 40 3
3 50 2
4 70 1
0
예제 #2
7 3 1
1 40 3
3 50 2
4 70 1
1
예제 #3
7 3 2
1 40 3
3 50 2
4 70 1
0
로그인해야 코드를 작성할 수 있어요.