시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 556 | 198 | 173 | 49.008% |
영선이는 과대 포장으로 유명한 남규 회사에서 아르바이트를 한다. 영선이는 여러 박스들을 여러겹으로 포장하는 업무를 맡았다. 박스를 포장할 때 규칙이 있는데, 일단 박스를 일렬로 주어진다. 그리고 앞에 있는 박스가 뒤에 있는 박스보다 작아야지만, 뒤에 있는 박스에 넣을 수 있다. 뒤에 있는 박스를 앞에 있는 박스에 넣을 순 없다.
박스의 크기가 앞에서부터 일렬로 주어졌을 때, 최대한 박스안에 박스를 넣어 과대 포장한 박스 개수를 구하시오.
첫째 줄에는 박스의 개수 n이 주어진다.(1≤n≤5000)
다음 줄에는 박스의 크기 Ai가 앞에서부터 차례대로 주어진다.(1≤Ai≤100,000)
최대한 박스안에 박스를 넣어 과대 포장을 할 때, 그 박스들의 개수를 구하시오.
4 1 2 3 4
4
4 4 3 3 1
1