시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 (추가 시간 없음) | 1024 MB | 2262 | 1292 | 1045 | 60.265% |
$N$장의 카드가 좌우 일렬로 놓여있다. 각 카드에는 하나의 정수가 적혀있는데, 왼쪽에서 $i$번째 카드에 적혀있는 정수는 $A_i$다. ($1 ≤ i ≤ N$)
여러분은 $N$장의 카드 중 몇 장을 골라 제거할 수 있다. 이때, 제거되지 않은 카드의 순서는 유지된다.
예를 들어, $N = 5$, $A = [3, 1, 4, 1, 5]$라고 하자. 여러분이 두 번째와 다섯 번째 카드를 제거한다면, 남은 카드들에 적혀있는 수들은 왼쪽부터 차례대로 $3, 4, 1$이 된다. 즉, 남은 카드들 중 왼쪽에서 세 번째 카드에 적혀있는 수는 $1$이 된다.
몇 장의 카드를 골라 제거한 후, 남은 카드들 중 왼쪽에서 $x$번째 카드에 적혀있는 수가 정확히 $x$라면, 그 카드를 제자리 카드라고 부르자. 모든 남은 카드가 제자리 카드라면, 제자리 상태가 되었다고 하자.
예를 들어, $N = 8$, $A = [6, 1, 2, 3, 2, 4, 5, 10]$라고 하자. 여러분이 첫 번째, 다섯 번째, 여덟 번째 카드를 제거하면, 남은 카드들에 적혀있는 수들은 차례대로 $1, 2, 3, 4, 5$가 된다. 이때, 모든 남은 카드는 제자리 카드가 되며, 따라서 제자리 상태가 되었다.
만약, N = 6, A = [3, 4, 6, 10, 2, 5]라면, 제자리 상태가 되기 위해서는 모든 카드를 제거하여 남은 카드가 하나도 없도록 해야 한다.
모든 카드를 제거하면 항상 제자리 상태가 됨에 유의하라.
최소 몇 장의 카드를 제거해야 제자리 상태가 되는지 계산하는 프로그램을 작성하라.
첫 번째 줄에 정수 $N$이 주어진다.
두 번째 줄에 $N$ 개의 정수 $A_1, \dots , A_N$이 차례대로 주어진다.
첫 번째 줄에 답을 출력한다.
번호 | 배점 | 제한 |
---|---|---|
1 | 5 | $N = 1$. |
2 | 16 | $N ≤ 20$. |
3 | 28 | $N ≤ 1,500$. |
4 | 51 | 추가 제약 조건 없음. |
1 1
0
8 6 1 2 3 2 4 5 10
3
6 3 4 6 10 2 5
6
Olympiad > 한국정보올림피아드 > KOI 2022 2차대회 > 초등부 1번