시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 4501 | 1148 | 746 | 25.211% |
준규는 새 RPG 게임을 시작했다. 이 게임에서 캐릭터는 2가지 스탯을 가지고 있다. 하나는 힘(STR)이고, 다른 하나는 지력(INT)이다. 캐릭터를 생성했을 때, 두 스탯은 모두 1이다.
게임에는 총 N개의 퀘스트가 있다. i번째 퀘스트를 깨려면 캐릭터의 힘이 STR[i]보다 크거나 같거나, 지력이 INT[i]보다 크거나 같아야 한다. 이 퀘스트를 깨면, 스탯을 올릴 수 있는 포인트를 PNT[i]개 만큼 얻게 된다.
모든 퀘스트는 단 한 번만 깰 수 있으며, 퀘스트를 깨는 순서는 준규가 마음대로 정할 수 있다. 또, 퀘스트 보상으로 얻게되는 포인트로 준규 마음대로 스탯을 올릴 수 있다.
준규가 깰 수 있는 퀘스트 개수의 최댓값을 구하는 프로그램을 작성하시오.
첫째 줄에 퀘스트의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다.
둘째 줄부터 N개의 줄에 STR[i], INT[i], PNT[i]가 주어진다. 이 숫자는 모두 1,000보다 작거나 같은 자연수이다.
첫째 줄에 준규가 깰 수 있는 퀘스트 개수의 최댓값을 출력한다.
5 1 1 2 3 1 1 1 3 1 10 20 5 3 3 1
4
2 1 1 1 2 2 2
2
1 3 2 1
0
9 1 1 1 2 100 2 100 3 3 5 100 4 100 7 5 10 100 6 100 13 7 17 100 8 100 21 1
9
10 1 1 1 10 5 1 1 1 1 2 8 2 16 3 1 12 5 1 13 3 2 19 16 3 12 19 5 8 20 1
7