지게차 투입
문제
한 물류 창고에는 컨베이어가 하나 있고, 그 위에 짐 N개가 왼쪽부터 한 줄로 놓여 있다. 컨베이어가 돌면 짐은 왼쪽에 있던 것부터 차례대로 하나씩 작업대 앞을 지나간다. 짐마다 보관 번호가 하나씩 적혀 있는데, 이 번호는 그 짐을 넣어야 하는 선반의 번호다.
짐을 집어 선반에 넣는 일은 지게차가 한다. 지게차를 새로 한 대 투입하면 그 지게차는 지금 작업대 앞을 지나가는 짐을 집는다. 그 뒤로 그 지게차는 선반을 한 칸씩 내려가며 일하기 때문에, 자기가 마지막에 집은 짐의 보관 번호보다 정확히 1 작은 번호가 적힌 짐만 집을 수 있다. 번호가 그보다 크거나 2 이상 작은 짐은 집지 못한다. 한 짐은 한 대가 집으며, 이미 투입한 지게차는 창고를 떠나지 않고 자기 차례를 기다린다.
작업대 앞을 지나가는 짐은 하나도 빠짐없이 어느 한 지게차가 집어야 한다. N개의 짐에 적힌 보관 번호가 왼쪽부터 차례대로 주어졌을 때, 모든 짐을 집으려면 지게차가 최소 몇 대 필요한지 구하는 프로그램을 작성하여라.
예를 들어 N=5개의 짐에 적힌 보관 번호가 왼쪽부터 다음의 표와 같다고 해보자.
| 순서 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 보관 번호 | 2 | 1 | 5 | 4 | 3 |
첫 번째 짐의 번호는 2인데 일하고 있는 지게차가 없으므로 1호를 투입한다. 1호는 번호가 2인 짐을 집었으므로 다음에는 번호가 1인 짐만 집을 수 있다. 두 번째 짐의 번호가 1이므로 1호가 그대로 집는다. 세 번째 짐의 번호는 5인데 1호는 이제 번호가 0인 짐을 기다리고 있으므로 집지 못한다. 그래서 2호를 투입한다. 네 번째 짐의 번호는 4이고 다섯 번째 짐의 번호는 3이므로 2호가 이어서 집는다.
| 순서 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 보관 번호 | 2 | 1 | 5 | 4 | 3 |
| 집는 지게차 | 1호 | 1호 | 2호 | 2호 | 2호 |
| 새로 투입했는가 | 투입 | 아니다 | 투입 | 아니다 | 아니다 |
지게차를 두 대 썼으므로 현재 예시에서 정답은 2다.
입출력 예시
예시 1
입력
5 2 1 5 4 3
출력
2
예시 2
입력
10 12 5 15 3 12 13 16 7 20 13
출력
10
예시 3
입력
1 8
출력
1
입력 조건
가장 먼저 짐의 수 N이 첫째 줄에 주어진다. N은 1 이상 1,000,000 이하의 자연수다.
이어서 둘째 줄에 N개의 짐에 적힌 보관 번호가 왼쪽에 놓인 것부터 차례대로 공백 하나로 구분되어 주어진다. 각 보관 번호는 1 이상 1,000,000 이하의 자연수다. 보관 번호는 둘째 줄 한 줄에 모두 주어지며, 같은 번호가 여러 짐에 적혀 있을 수도 있다. 입력은 모두 두 줄이다.
출력 조건
모든 짐을 집는 데 필요한 지게차의 최소 대수를 첫째 줄에 출력한다.
수 하나를 출력하고 줄을 바꾼다. 앞뒤에 다른 글자나 공백은 붙이지 않는다.
요구사항
- 입력은 표준 입력으로 받고 답은 표준 출력으로 내보냅니다
- 짐은 입력에 주어진 순서대로 하나씩 지나갑니다. 순서를 바꿀 수는 없습니다
- 지게차는 자기가 마지막에 집은 번호보다 정확히 1 작은 번호만 집을 수 있습니다
- 보관 번호는 둘째 줄 한 줄에 N개가 모두 주어집니다
- N이 1,000,000까지 올라가므로 짐마다 지게차를 모두 훑는 방법으로는 시간 안에 끝나지 않습니다
- 출력은 수 하나와 줄바꿈뿐입니다
- 채점은 출력을 기대값과 글자 하나까지 견줍니다
- 표준 입력으로 읽고 표준 출력으로 내보내는 프로그램을 짜야 합니다
- 쓸 수 있는 말은 파이썬, 자바스크립트입니다
- 메모리 제한은 256MB입니다. 브라우저에서는 재지 않고 적기만 합니다
- 시간 제한은 출제자의 정답 코드를 같은 런타임에서 재서 정합니다
- 이 문제는 프롬프트가 아니라 코드를 냅니다. 그 코드는 이 기기의 브라우저에서 돌고, 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다. 실행 시간은 각자 기기가 적어 보내는 값이라, 코드와 기기 정보를 순위표에 같이 내걸어 둡니다.
- 케이스는 15개이고, 그 가운데 3개는 입력과 기대 출력을 함께 보여 줍니다. 나머지는 제출할 때만 쓰이고 화면에는 보여 주지 않습니다.
- 케이스 15개를 전부 통과해야 해결입니다.
예시
공개 케이스 3개입니다. 채점에는 숨은 케이스가 함께 쓰입니다. 케이스 15개를 전부 통과해야 해결입니다.
1 8
1
10 12 5 15 3 12 13 16 7 20 13
10
5 2 1 5 4 3
2
풀이
코드는 이 기기에서돕니다. 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다.
제출은 로그인 하셔야 됩니다. 공개 케이스로 돌려보는 것은 로그인 없이도 됩니다.
공개 케이스 3개로 돌려보기가 됩니다. 제출하면 숨은 케이스까지 돕니다.
이 문제를 푼 사람
아직 없습니다. 첫 번째가 되실 수 있습니다.