시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 17 2 2 16.667%

문제

아래 왼쪽 그림은 성냥개비 2×(3×4) = (24)개로 완전 3×3 그리드를 만든 것이다. 모든 성냥개비의 길이는 1이다. 그리드에는 다양한 크기의 정사각형이 있다. 정사각형의 크기는 변의 길이와 같다. 왼쪽 그림에 크기가 1인 정사각형은 9개, 2인 정사각형은 4개, 3인 정사각형은 1개가 있다.

완전 그리드에 있는 성냥개비에 아래 왼쪽 그림에 나와있는 것처럼 왼쪽부터 오른쪽, 위부터 아래 순서로 번호를 매길 수 있다. 완전 그리드에서 성냥개비 일부를 제거하면, 정사각형의 일부를 파괴할 수 있고, 완전하지 않은 그리드를 만들 수 있다. 오른쪽 그림은 완전하지 않은 3×3 그리드이며, 12, 17, 23번 성냥개비를 제거했을 때이다. 이 결과로 크기가 1인 정사각형 5개, 2인 정사각형 3개, 3인 정사각형 1개가 제거되고, 크기가 1인 정사각형이 3개, 2인 정사각형이 1개 남는다.

2n(n+1)개를 넘지 않는 성냥개비로 만든 완전 또는 완전하지 않은 n×n 그리드가 주어진다. (n ≤ 5) 이 때, n×n 그리드의 모든 정사각형을 파괴하기 위해 제거해야 하는 성냥개비 개수의 최소값을 구하는 프로그램을 작성하시오.

입력

입력은 T개의 테스트 케이스로 이루어져 있다. 첫째 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 두 줄로 이루어져 있다.

첫째 줄에는 5를 넘지 않는 자연수 n이 주어진다. n은 그리드의 크기이다. 둘째 줄에는 음이 아닌 정수 k가 주어진다. k는 n×n 그리드에서 제거된 성냥개비의 개수이다. k의 다음에는 제거한 성냥개비의 번호가 주어진다. k가 0인 경우에는 입력으로 완전한 그리드가 주어진 것이고, 아닌 경우에는 완전하지 않는 그리드가 주어진 것이다.

출력

각 테스트 케이스에 대해서, 입력으로 주어진 그리드에서 모든 정사각형을 파괴하기 위해 제거해야 하는 성냥개비 개수의 최소값을 출력한다.

예제 입력

2
2
0
3
3 12 17 23

예제 출력

3
3

힌트

출처

ACM-ICPC > Regionals > Asia > Korea > Asia Regional - Taejon 2001 H번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: muckworm