시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 37 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인 경우에는 입력으로 완전한 그리드가 주어진 것이고, 아닌 경우에는 완전하지 않는 그리드가 주어진 것이다.

출력

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

예제 입력 1

2
2
0
3
3 12 17 23

예제 출력 1

3
3
W3sicHJvYmxlbV9pZCI6IjczNTAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTUgXHViZDgwXHVjMjE4XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1NDRcdWI3OTggXHVjNjdjXHVjYWJkIFx1YWRmOFx1YjliY1x1Yzc0MCBcdWMxMzFcdWIwZTVcdWFjMWNcdWJlNDQgMiZ0aW1lczsoMyZ0aW1lczs0KSA9ICgyNClcdWFjMWNcdWI4NWMgXHVjNjQ0XHVjODA0IDMmdGltZXM7MyBcdWFkZjhcdWI5YWNcdWI0ZGNcdWI5N2MgXHViOWNjXHViNGUwIFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHViYWE4XHViNGUwIFx1YzEzMVx1YjBlNVx1YWMxY1x1YmU0NFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgMVx1Yzc3NFx1YjJlNC4gXHVhZGY4XHViOWFjXHViNGRjXHVjNWQwXHViMjk0IFx1YjJlNFx1YzU5MVx1ZDU1YyBcdWQwNmNcdWFlMzBcdWM3NTggXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YjI5NCBcdWJjYzBcdWM3NTggXHVhZTM4XHVjNzc0XHVjNjQwIFx1YWMxOVx1YjJlNC4gXHVjNjdjXHVjYWJkIFx1YWRmOFx1YjliY1x1YzVkMCBcdWQwNmNcdWFlMzBcdWFjMDAgMVx1Yzc3OCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDAgOVx1YWMxYywgMlx1Yzc3OCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDAgNFx1YWMxYywgM1x1Yzc3OCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDAgMVx1YWMxY1x1YWMwMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzY0NFx1YzgwNCBcdWFkZjhcdWI5YWNcdWI0ZGNcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzEzMVx1YjBlNVx1YWMxY1x1YmU0NFx1YzVkMCBcdWM1NDRcdWI3OTggXHVjNjdjXHVjYWJkIFx1YWRmOFx1YjliY1x1YzVkMCBcdWIwOThcdWM2NDBcdWM3ODhcdWIyOTQgXHVhYzgzXHVjYzk4XHViN2ZjIFx1YzY3Y1x1Y2FiZFx1YmQ4MFx1ZDEzMCBcdWM2MjRcdWI5NzhcdWNhYmQsIFx1YzcwNFx1YmQ4MFx1ZDEzMCBcdWM1NDRcdWI3OTggXHVjMjFjXHVjMTFjXHViODVjIFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWI5ZTRcdWFlMzggXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNjQ0XHVjODA0IFx1YWRmOFx1YjlhY1x1YjRkY1x1YzVkMFx1YzExYyBcdWMxMzFcdWIwZTVcdWFjMWNcdWJlNDQgXHVjNzdjXHViZDgwXHViOTdjIFx1YzgxY1x1YWM3MFx1ZDU1OFx1YmE3NCwgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNzU4IFx1Yzc3Y1x1YmQ4MFx1Yjk3YyBcdWQzMGNcdWFkMzRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YWNlMCwgXHVjNjQ0XHVjODA0XHVkNTU4XHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWFkZjhcdWI5YWNcdWI0ZGNcdWI5N2MgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWFkZjhcdWI5YmNcdWM3NDAgXHVjNjQ0XHVjODA0XHVkNTU4XHVjOWMwIFx1YzU0YVx1Yzc0MCAzJnRpbWVzOzMgXHVhZGY4XHViOWFjXHViNGRjXHVjNzc0XHViYTcwLCAxMiwgMTcsIDIzXHViYzg4IFx1YzEzMVx1YjBlNVx1YWMxY1x1YmU0NFx1Yjk3YyBcdWM4MWNcdWFjNzBcdWQ1ODhcdWM3NDQgXHViNTRjXHVjNzc0XHViMmU0LiBcdWM3NzQgXHVhY2IwXHVhY2ZjXHViODVjIFx1ZDA2Y1x1YWUzMFx1YWMwMCAxXHVjNzc4IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNSA1XHVhYzFjLCAyXHVjNzc4IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNSAzXHVhYzFjLCAzXHVjNzc4IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNSAxXHVhYzFjXHVhYzAwIFx1YzgxY1x1YWM3MFx1YjQxOFx1YWNlMCwgXHVkMDZjXHVhZTMwXHVhYzAwIDFcdWM3NzggXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNzc0IDNcdWFjMWMsIDJcdWM3NzggXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNzc0IDFcdWFjMWMgXHViMGE4XHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL21hdGNoc3FhdXJlKDEpLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjMxOHB4OyB3aWR0aDo2MjlweFwiIFwvPjxcL3A+XHJcblxyXG48cD4ybihuKzEpXHVhYzFjXHViOTdjIFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTQgXHVjMTMxXHViMGU1XHVhYzFjXHViZTQ0XHViODVjIFx1YjljY1x1YjRlMCBcdWM2NDRcdWM4MDQgXHViNjEwXHViMjk0IFx1YzY0NFx1YzgwNFx1ZDU1OFx1YzljMCBcdWM1NGFcdWM3NDAgbiZ0aW1lcztuIFx1YWRmOFx1YjlhY1x1YjRkY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIChuICZsZTsgNSkgXHVjNzc0XHViNTRjLCBuJnRpbWVzO24gXHVhZGY4XHViOWFjXHViNGRjXHVjNzU4IFx1YmFhOFx1YjRlMCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDQgXHVkMzBjXHVhZDM0XHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWM4MWNcdWFjNzBcdWQ1NzRcdWM1N2MgXHVkNTU4XHViMjk0IFx1YzEzMVx1YjBlNVx1YWMxY1x1YmU0NCBcdWFjMWNcdWMyMThcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFRcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWI0NTAgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgNVx1Yjk3YyBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0IFx1Yzc5MFx1YzVmMFx1YzIxOCBuXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gblx1Yzc0MCBcdWFkZjhcdWI5YWNcdWI0ZGNcdWM3NTggXHVkMDZjXHVhZTMwXHVjNzc0XHViMmU0LiBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1Yzc0Y1x1Yzc3NCBcdWM1NDRcdWIyY2MgXHVjODE1XHVjMjE4IGtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBrXHViMjk0IG4mdGltZXM7biBcdWFkZjhcdWI5YWNcdWI0ZGNcdWM1ZDBcdWMxMWMgXHVjODFjXHVhYzcwXHViNDFjIFx1YzEzMVx1YjBlNVx1YWMxY1x1YmU0NFx1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NzRcdWIyZTQuIGtcdWM3NTggXHViMmU0XHVjNzRjXHVjNWQwXHViMjk0IFx1YzgxY1x1YWM3MFx1ZDU1YyBcdWMxMzFcdWIwZTVcdWFjMWNcdWJlNDRcdWM3NTggXHViYzg4XHVkNjM4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4ga1x1YWMwMCAwXHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjNjQ0XHVjODA0XHVkNTVjIFx1YWRmOFx1YjlhY1x1YjRkY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVhYzgzXHVjNzc0XHVhY2UwLCBcdWM1NDRcdWIyY2MgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YzY0NFx1YzgwNFx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTQgXHVhZGY4XHViOWFjXHViNGRjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YWRmOFx1YjlhY1x1YjRkY1x1YzVkMFx1YzExYyBcdWJhYThcdWI0ZTAgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNzQ0IFx1ZDMwY1x1YWQzNFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVjODFjXHVhYzcwXHVkNTc0XHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWMxMzFcdWIwZTVcdWFjMWNcdWJlNDQgXHVhYzFjXHVjMjE4XHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNzM1MCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlNxdWFyZSBEZXN0cm95ZXIiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBsZWZ0IGZpZ3VyZSBiZWxvdyBzaG93cyBhIGNvbXBsZXRlIDMmdGltZXM7MyBncmlkIG1hZGUgd2l0aCAyJnRpbWVzOygzJnRpbWVzOzQpICg9IDI0KSBtYXRjaHN0aWNrcy4gVGhlIGxlbmd0aHMgb2YgYWxsIG1hdGNoc3RpY2tzIGFyZSBvbmUuIFlvdSBjYW4gZmluZCBtYW55IHNxdWFyZXMgb2YgZGlmZmVyZW50IHNpemVzIGluIHRoZSBncmlkLiBUaGUgc2l6ZSBvZiBhIHNxdWFyZSBpcyB0aGUgbGVuZ3RoIG9mIGl0cyBzaWRlLiBJbiB0aGUgZ3JpZCBzaG93biBpbiB0aGUgbGVmdCBmaWd1cmUsIHRoZXJlIGFyZSA5IHNxdWFyZXMgb2Ygc2l6ZSBvbmUsIDQgc3F1YXJlcyBvZiBzaXplIHR3bywgYW5kIDEgc3F1YXJlIG9mIHNpemUgdGhyZWUuPFwvcD5cclxuXHJcbjxwPkVhY2ggbWF0Y2hzdGljayBvZiB0aGUgY29tcGxldGUgZ3JpZCBpcyBpZGVudGlmaWVkIHdpdGggYSB1bmlxdWUgbnVtYmVyIHdoaWNoIGlzIGFzc2lnbmVkIGZyb20gbGVmdCB0byByaWdodCBhbmQgZnJvbSB0b3AgdG8gYm90dG9tIGFzIHNob3duIGluIHRoZSBsZWZ0IGZpZ3VyZS4gSWYgeW91IHRha2Ugc29tZSBtYXRjaHN0aWNrcyBvdXQgZnJvbSB0aGUgY29tcGxldGUgZ3JpZCwgdGhlbiBzb21lIHNxdWFyZXMgaW4gdGhlIGdyaWQgd2lsbCBiZSBkZXN0cm95ZWQsIHdoaWNoIHJlc3VsdHMgaW4gYW4gaW5jb21wbGV0ZSAzJnRpbWVzOzMgZ3JpZC4gVGhlIHJpZ2h0IGZpZ3VyZSBpbGx1c3RyYXRlcyBhbiBpbmNvbXBsZXRlIDMmdGltZXM7MyBncmlkIGFmdGVyIHJlbW92aW5nIHRocmVlIG1hdGNoc3RpY2tzIG51bWJlcmVkIHdpdGggMTIsIDE3IGFuZCAyMy4gVGhpcyByZW1vdmFsIGRlc3Ryb3lzIDUgc3F1YXJlcyBvZiBzaXplIG9uZSwgMyBzcXVhcmVzIG9mIHNpemUgdHdvLCBhbmQgMSBzcXVhcmUgb2Ygc2l6ZSB0aHJlZS4gQ29uc2VxdWVudGx5LCB0aGUgaW5jb21wbGV0ZSBncmlkIGRvZXMgbm90IGhhdmUgc3F1YXJlcyBvZiBzaXplIHRocmVlLCBidXQgc3RpbGwgaGFzIDQgc3F1YXJlcyBvZiBzaXplIG9uZSBhbmQgMSBzcXVhcmUgb2Ygc2l6ZSB0d288XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9tYXRjaHNxYXVyZSgxKS5wbmdcIiBzdHlsZT1cImhlaWdodDozMThweDsgd2lkdGg6NjI5cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+QXMgaW5wdXQsIHlvdSBhcmUgZ2l2ZW4gYSAoY29tcGxldGUgb3IgaW5jb21wbGV0ZSkgbiAmdGltZXM7IG4gZ3JpZCBtYWRlIHdpdGggbm8gbW9yZSB0aGFuIDJuKG4gKzEpIG1hdGNoc3RpY2tzIGZvciBhIG5hdHVyYWwgbnVtYmVyIG4gJmxlOyA1IC4gWW91ciB0YXNrIGlzIHRvIGNvbXB1dGUgdGhlIG1pbmltdW0gbnVtYmVyIG9mIG1hdGNoc3RpY2tzIHRha2VuIG91dCB0byBkZXN0cm95IGFsbCB0aGUgc3F1YXJlcyBleGlzdGluZyBpbiB0aGUgaW5wdXQgbiAmdGltZXM7IG4gZ3JpZC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb25zaXN0cyBvZiBUIHRlc3QgY2FzZXMuIFRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyAoVCApIGlzIGdpdmVuIGluIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBmaWxlLiBFYWNoIHRlc3QgY2FzZSBjb25zaXN0cyBvZiB0d28gbGluZXM6IFRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIGEgbmF0dXJhbCBudW1iZXIgbiAsIG5vdCBncmVhdGVyIHRoYW4gNSwgd2hpY2ggaW1wbGllcyB5b3UgYXJlIGdpdmVuIGEgKGNvbXBsZXRlIG9yIGluY29tcGxldGUpIG4gJnRpbWVzOyBuIGdyaWQgYXMgaW5wdXQsIGFuZCB0aGUgc2Vjb25kIGxpbmUgYmVnaW5zIHdpdGggYSBub25uZWdhdGl2ZSBpbnRlZ2VyIGsgLCB0aGUgbnVtYmVyIG9mIG1hdGNoc3RpY2tzIHRoYXQgYXJlIG1pc3NpbmcgZnJvbSB0aGUgY29tcGxldGUgbiAmdGltZXM7IG4gZ3JpZCwgZm9sbG93ZWQgYnkgayBudW1iZXJzIHNwZWNpZnlpbmcgdGhlIG1hdGNoc3RpY2tzLiBOb3RlIHRoYXQgaWYgayBpcyBlcXVhbCB0byB6ZXJvLCB0aGVuIHRoZSBpbnB1dCBncmlkIGlzIGEgY29tcGxldGUgbiAmdGltZXM7IG4gZ3JpZDsgb3RoZXJ3aXNlLCB0aGUgaW5wdXQgZ3JpZCBpcyBhbiBpbmNvbXBsZXRlIG4gJnRpbWVzOyBuIGdyaWQgc3VjaCB0aGF0IHRoZSBzcGVjaWZpZWQgayBtYXRjaHN0aWNrcyBhcmUgbWlzc2luZyBmcm9tIHRoZSBjb21wbGV0ZSBuICZ0aW1lczsgbiBncmlkLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlByaW50IGV4YWN0bHkgb25lIGxpbmUgZm9yIGVhY2ggdGVzdCBjYXNlLiBUaGUgbGluZSBzaG91bGQgY29udGFpbiB0aGUgbWluaW11bSBudW1iZXIgb2YgbWF0Y2hzdGlja3MgdGhhdCBoYXZlIHRvIGJlIHRha2VuIG91dCB0byBkZXN0cm95IGFsbCB0aGUgc3F1YXJlcyBpbiB0aGUgaW5wdXQgZ3JpZC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

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

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