| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 167 | 79 | 74 | 58.268% |
도윤이에게는 $N$행 $N$열의 격자로 이루어진 모눈종이가 하나 있습니다. 도윤이가 모눈종이를 자습실에 두고 놀다 왔더니 다른 친구가 각 행마다 정확히 한 칸을 골라 총 $N$개의 낙서를 하고 갔습니다. 모눈종이를 버릴 수 없는 도윤이는 여기에 아래 조건을 만족하도록 색종이를 덧붙여 낙서를 완전히 가리려고 합니다.
아래 그림의 왼쪽은 $K = 6$일 때 위 조건을 만족하도록 색종이를 붙인 모습이며, 오른쪽은 두 색종이 모두 $3$행을 공통으로 덮으므로 위 조건을 만족하지 않습니다.
$N$, $K$가 주어지고 각 행에 친구가 낙서한 위치가 주어질 때 도윤이에게 필요한 색종이 수의 최솟값을 구해봅시다.
첫째 줄에 양의 정수 $N$, $K$가 공백으로 구분되어 주어집니다.
둘째 줄부터 각 행에서 친구가 낙서한 위치를 나타내는 정수 $a_{1},a_{2},\dots , a_{N}$이 공백으로 구분되어 주어집니다. 이는 $i$행 $a_{i}$열 위치에 친구가 낙서를 남겼다는 뜻입니다.
첫째 줄에 필요한 색종이 수의 최솟값을 출력합니다.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 5 | $K = 1$ |
| 2 | 13 | $a_1=a_2=\cdots =a_{N}$ |
| 3 | 28 | $a_1 \le a_2 \le \cdots \le a_{N}$ |
| 4 | 54 | 추가 제한 조건이 없습니다. |
5 6 2 1 1 5 4
2
5 2 2 1 1 5 4
4
5 4 2 1 1 5 4
3
School > 서울과학고등학교 > 2026 SciCom Qualification Test B번