시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 46 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+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YWRmOFx1YjlhY1x1YjRkY1x1YzVkMFx1YzExYyBcdWJhYThcdWI0ZTAgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNzQ0IFx1ZDMwY1x1YWQzNFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVjODFjXHVhYzcwXHVkNTc0XHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWMxMzFcdWIwZTVcdWFjMWNcdWJlNDQgXHVhYzFjXHVjMjE4XHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI3MzUwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU3F1YXJlIERlc3Ryb3llciIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIGxlZnQgZmlndXJlIGJlbG93IHNob3dzIGEgY29tcGxldGUgMyZ0aW1lczszIGdyaWQgbWFkZSB3aXRoIDImdGltZXM7KDMmdGltZXM7NCkgKD0gMjQpIG1hdGNoc3RpY2tzLiBUaGUgbGVuZ3RocyBvZiBhbGwgbWF0Y2hzdGlja3MgYXJlIG9uZS4gWW91IGNhbiBmaW5kIG1hbnkgc3F1YXJlcyBvZiBkaWZmZXJlbnQgc2l6ZXMgaW4gdGhlIGdyaWQuIFRoZSBzaXplIG9mIGEgc3F1YXJlIGlzIHRoZSBsZW5ndGggb2YgaXRzIHNpZGUuIEluIHRoZSBncmlkIHNob3duIGluIHRoZSBsZWZ0IGZpZ3VyZSwgdGhlcmUgYXJlIDkgc3F1YXJlcyBvZiBzaXplIG9uZSwgNCBzcXVhcmVzIG9mIHNpemUgdHdvLCBhbmQgMSBzcXVhcmUgb2Ygc2l6ZSB0aHJlZS48XC9wPlxyXG5cclxuPHA+RWFjaCBtYXRjaHN0aWNrIG9mIHRoZSBjb21wbGV0ZSBncmlkIGlzIGlkZW50aWZpZWQgd2l0aCBhIHVuaXF1ZSBudW1iZXIgd2hpY2ggaXMgYXNzaWduZWQgZnJvbSBsZWZ0IHRvIHJpZ2h0IGFuZCBmcm9tIHRvcCB0byBib3R0b20gYXMgc2hvd24gaW4gdGhlIGxlZnQgZmlndXJlLiBJZiB5b3UgdGFrZSBzb21lIG1hdGNoc3RpY2tzIG91dCBmcm9tIHRoZSBjb21wbGV0ZSBncmlkLCB0aGVuIHNvbWUgc3F1YXJlcyBpbiB0aGUgZ3JpZCB3aWxsIGJlIGRlc3Ryb3llZCwgd2hpY2ggcmVzdWx0cyBpbiBhbiBpbmNvbXBsZXRlIDMmdGltZXM7MyBncmlkLiBUaGUgcmlnaHQgZmlndXJlIGlsbHVzdHJhdGVzIGFuIGluY29tcGxldGUgMyZ0aW1lczszIGdyaWQgYWZ0ZXIgcmVtb3ZpbmcgdGhyZWUgbWF0Y2hzdGlja3MgbnVtYmVyZWQgd2l0aCAxMiwgMTcgYW5kIDIzLiBUaGlzIHJlbW92YWwgZGVzdHJveXMgNSBzcXVhcmVzIG9mIHNpemUgb25lLCAzIHNxdWFyZXMgb2Ygc2l6ZSB0d28sIGFuZCAxIHNxdWFyZSBvZiBzaXplIHRocmVlLiBDb25zZXF1ZW50bHksIHRoZSBpbmNvbXBsZXRlIGdyaWQgZG9lcyBub3QgaGF2ZSBzcXVhcmVzIG9mIHNpemUgdGhyZWUsIGJ1dCBzdGlsbCBoYXMgNCBzcXVhcmVzIG9mIHNpemUgb25lIGFuZCAxIHNxdWFyZSBvZiBzaXplIHR3bzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL21hdGNoc3FhdXJlKDEpLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjMxOHB4OyB3aWR0aDo2MjlweFwiIFwvPjxcL3A+XHJcblxyXG48cD5BcyBpbnB1dCwgeW91IGFyZSBnaXZlbiBhIChjb21wbGV0ZSBvciBpbmNvbXBsZXRlKSBuICZ0aW1lczsgbiBncmlkIG1hZGUgd2l0aCBubyBtb3JlIHRoYW4gMm4obiArMSkgbWF0Y2hzdGlja3MgZm9yIGEgbmF0dXJhbCBudW1iZXIgbiAmbGU7IDUgLiBZb3VyIHRhc2sgaXMgdG8gY29tcHV0ZSB0aGUgbWluaW11bSBudW1iZXIgb2YgbWF0Y2hzdGlja3MgdGFrZW4gb3V0IHRvIGRlc3Ryb3kgYWxsIHRoZSBzcXVhcmVzIGV4aXN0aW5nIGluIHRoZSBpbnB1dCBuICZ0aW1lczsgbiBncmlkLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnNpc3RzIG9mIFQgdGVzdCBjYXNlcy4gVGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIChUICkgaXMgZ2l2ZW4gaW4gdGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGZpbGUuIEVhY2ggdGVzdCBjYXNlIGNvbnNpc3RzIG9mIHR3byBsaW5lczogVGhlIGZpcnN0IGxpbmUgY29udGFpbnMgYSBuYXR1cmFsIG51bWJlciBuICwgbm90IGdyZWF0ZXIgdGhhbiA1LCB3aGljaCBpbXBsaWVzIHlvdSBhcmUgZ2l2ZW4gYSAoY29tcGxldGUgb3IgaW5jb21wbGV0ZSkgbiAmdGltZXM7IG4gZ3JpZCBhcyBpbnB1dCwgYW5kIHRoZSBzZWNvbmQgbGluZSBiZWdpbnMgd2l0aCBhIG5vbm5lZ2F0aXZlIGludGVnZXIgayAsIHRoZSBudW1iZXIgb2YgbWF0Y2hzdGlja3MgdGhhdCBhcmUgbWlzc2luZyBmcm9tIHRoZSBjb21wbGV0ZSBuICZ0aW1lczsgbiBncmlkLCBmb2xsb3dlZCBieSBrIG51bWJlcnMgc3BlY2lmeWluZyB0aGUgbWF0Y2hzdGlja3MuIE5vdGUgdGhhdCBpZiBrIGlzIGVxdWFsIHRvIHplcm8sIHRoZW4gdGhlIGlucHV0IGdyaWQgaXMgYSBjb21wbGV0ZSBuICZ0aW1lczsgbiBncmlkOyBvdGhlcndpc2UsIHRoZSBpbnB1dCBncmlkIGlzIGFuIGluY29tcGxldGUgbiAmdGltZXM7IG4gZ3JpZCBzdWNoIHRoYXQgdGhlIHNwZWNpZmllZCBrIG1hdGNoc3RpY2tzIGFyZSBtaXNzaW5nIGZyb20gdGhlIGNvbXBsZXRlIG4gJnRpbWVzOyBuIGdyaWQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+UHJpbnQgZXhhY3RseSBvbmUgbGluZSBmb3IgZWFjaCB0ZXN0IGNhc2UuIFRoZSBsaW5lIHNob3VsZCBjb250YWluIHRoZSBtaW5pbXVtIG51bWJlciBvZiBtYXRjaHN0aWNrcyB0aGF0IGhhdmUgdG8gYmUgdGFrZW4gb3V0IHRvIGRlc3Ryb3kgYWxsIHRoZSBzcXVhcmVzIGluIHRoZSBpbnB1dCBncmlkLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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

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