장난감 생산 > 문제은행



실전대비 Level9

1896 : 장난감 생산

제한시간: 1000 ms    메모리제한: 128 MB
해결횟수: 3 회    시도횟수: 4 회   



진욱이는 열심히 일하는 장난감 공장의 직원이다.

실제로 진욱이는 앞으로 다가올 N(1≤N≤1,000,000)시간(편의상 시간구간은 순서대로 0부터 N-1의 번호를 붙인다.) 

동안 최대한 많은 장남감을 만들고자 한다.

공장장인 동훈이는 M(1≤M≤1,000)개의 서로 겹칠 수 있는 장난감을 만들 수 있는 시간 목록을 가지고 있다. 

매 구간은 시작시간(0이상 N-1이하), 종료 시간(시작시간보다 크고 N 이하)과 

해당 구간내에서 그 구간 동안 몇 개의 장난감을 만들 수 있는 효율(1이상 1,000,000이하)이 주어지며, 

동훈이는 진욱이에게 구간의 시작 시간에 장난감 만들기를 시작하도록 지시할 수 있고, 

종료 시간에 장난감 만들기를 종료하도록 지시 할 수 있다. 

 

그 외의 시간에는 명령하지 못하며, 진욱이는 시작한 구간 내에서만 장난감을 만들 수 있다.

하지만 진욱이도 인간이기 때문에, 

장난감을 만드는 구간이 종료 되면 반드시 최소한 R(1≤R≤N)분의 시간을 쉬어야 장난감을 만들 수 있다. 

만약 5분에 일을 마치고 5분을 쉬어야 한다면, 진욱이는 10분부터 다시 작업을 시작할 수 있게 된다. 

동훈이가 가진 구간의 정보가 주어졌을 때 진욱이가 제작 가능한 최대한의 장난감 개수를 알아보는 프로그램을 작성해보자.




첫 번째 줄에는 N과 M과 R이 공백을 사이에 두고 주어진다.

그 다음 줄부터 M개의 줄마다 한 구간의 시작시간 도착시간 효율이 공백을 사이에 두고 주어진다.




진욱이가 N시간 동안 만들 수 있는 장난감의 개수를 출력한다.



12 4 2
1 2 8
10 12 19
3 6 24
7 10 31
43



HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 031-388-0999 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.