시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 34 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+XHJcblxyXG48cD4ybihuKzEpXHVhYzFjXHViOTdjIFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTQgXHVjMTMxXHViMGU1XHVhYzFjXHViZTQ0XHViODVjIFx1YjljY1x1YjRlMCBcdWM2NDRcdWM4MDQgXHViNjEwXHViMjk0IFx1YzY0NFx1YzgwNFx1ZDU1OFx1YzljMCBcdWM1NGFcdWM3NDAgbiZ0aW1lcztuIFx1YWRmOFx1YjlhY1x1YjRkY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIChuICZsZTsgNSkgXHVjNzc0IFx1YjU0YywgbiZ0aW1lcztuIFx1YWRmOFx1YjlhY1x1YjRkY1x1Yzc1OCBcdWJhYThcdWI0ZTAgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNzQ0IFx1ZDMwY1x1YWQzNFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVjODFjXHVhYzcwXHVkNTc0XHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWMxMzFcdWIwZTVcdWFjMWNcdWJlNDQgXHVhYzFjXHVjMjE4XHVjNzU4IFx1Y2Q1Y1x1YzE4Y1x1YWMxMlx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBUXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHViNDUwIFx1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IDVcdWI5N2MgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NCBcdWM3OTBcdWM1ZjBcdWMyMTggblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIG5cdWM3NDAgXHVhZGY4XHViOWFjXHViNGRjXHVjNzU4IFx1ZDA2Y1x1YWUzMFx1Yzc3NFx1YjJlNC4gXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM3NGNcdWM3NzQgXHVjNTQ0XHViMmNjIFx1YzgxNVx1YzIxOCBrXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4ga1x1YjI5NCBuJnRpbWVzO24gXHVhZGY4XHViOWFjXHViNGRjXHVjNWQwXHVjMTFjIFx1YzgxY1x1YWM3MFx1YjQxYyBcdWMxMzFcdWIwZTVcdWFjMWNcdWJlNDRcdWM3NTggXHVhYzFjXHVjMjE4XHVjNzc0XHViMmU0LiBrXHVjNzU4IFx1YjJlNFx1Yzc0Y1x1YzVkMFx1YjI5NCBcdWM4MWNcdWFjNzBcdWQ1NWMgXHVjMTMxXHViMGU1XHVhYzFjXHViZTQ0XHVjNzU4IFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIGtcdWFjMDAgMFx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzY0NFx1YzgwNFx1ZDU1YyBcdWFkZjhcdWI5YWNcdWI0ZGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YWM4M1x1Yzc3NFx1YWNlMCwgXHVjNTQ0XHViMmNjIFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWM2NDRcdWM4MDRcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0IFx1YWRmOFx1YjlhY1x1YjRkY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNCBcdWFkZjhcdWI5YWNcdWI0ZGNcdWM1ZDBcdWMxMWMgXHViYWE4XHViNGUwIFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc0NCBcdWQzMGNcdWFkMzRcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YzgxY1x1YWM3MFx1ZDU3NFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVjMTMxXHViMGU1XHVhYzFjXHViZTQ0IFx1YWMxY1x1YzIxOFx1Yzc1OCBcdWNkNWNcdWMxOGNcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjczNTAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTcXVhcmUgRGVzdHJveWVyIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgbGVmdCBmaWd1cmUgYmVsb3cgc2hvd3MgYSBjb21wbGV0ZSAzJnRpbWVzOzMgZ3JpZCBtYWRlIHdpdGggMiZ0aW1lczsoMyZ0aW1lczs0KSAoPSAyNCkgbWF0Y2hzdGlja3MuIFRoZSBsZW5ndGhzIG9mIGFsbCBtYXRjaHN0aWNrcyBhcmUgb25lLiBZb3UgY2FuIGZpbmQgbWFueSBzcXVhcmVzIG9mIGRpZmZlcmVudCBzaXplcyBpbiB0aGUgZ3JpZC4gVGhlIHNpemUgb2YgYSBzcXVhcmUgaXMgdGhlIGxlbmd0aCBvZiBpdHMgc2lkZS4gSW4gdGhlIGdyaWQgc2hvd24gaW4gdGhlIGxlZnQgZmlndXJlLCB0aGVyZSBhcmUgOSBzcXVhcmVzIG9mIHNpemUgb25lLCA0IHNxdWFyZXMgb2Ygc2l6ZSB0d28sIGFuZCAxIHNxdWFyZSBvZiBzaXplIHRocmVlLjxcL3A+XHJcblxyXG48cD5FYWNoIG1hdGNoc3RpY2sgb2YgdGhlIGNvbXBsZXRlIGdyaWQgaXMgaWRlbnRpZmllZCB3aXRoIGEgdW5pcXVlIG51bWJlciB3aGljaCBpcyBhc3NpZ25lZCBmcm9tIGxlZnQgdG8gcmlnaHQgYW5kIGZyb20gdG9wIHRvIGJvdHRvbSBhcyBzaG93biBpbiB0aGUgbGVmdCBmaWd1cmUuIElmIHlvdSB0YWtlIHNvbWUgbWF0Y2hzdGlja3Mgb3V0IGZyb20gdGhlIGNvbXBsZXRlIGdyaWQsIHRoZW4gc29tZSBzcXVhcmVzIGluIHRoZSBncmlkIHdpbGwgYmUgZGVzdHJveWVkLCB3aGljaCByZXN1bHRzIGluIGFuIGluY29tcGxldGUgMyZ0aW1lczszIGdyaWQuIFRoZSByaWdodCBmaWd1cmUgaWxsdXN0cmF0ZXMgYW4gaW5jb21wbGV0ZSAzJnRpbWVzOzMgZ3JpZCBhZnRlciByZW1vdmluZyB0aHJlZSBtYXRjaHN0aWNrcyBudW1iZXJlZCB3aXRoIDEyLCAxNyBhbmQgMjMuIFRoaXMgcmVtb3ZhbCBkZXN0cm95cyA1IHNxdWFyZXMgb2Ygc2l6ZSBvbmUsIDMgc3F1YXJlcyBvZiBzaXplIHR3bywgYW5kIDEgc3F1YXJlIG9mIHNpemUgdGhyZWUuIENvbnNlcXVlbnRseSwgdGhlIGluY29tcGxldGUgZ3JpZCBkb2VzIG5vdCBoYXZlIHNxdWFyZXMgb2Ygc2l6ZSB0aHJlZSwgYnV0IHN0aWxsIGhhcyA0IHNxdWFyZXMgb2Ygc2l6ZSBvbmUgYW5kIDEgc3F1YXJlIG9mIHNpemUgdHdvPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvbWF0Y2hzcWF1cmUoMSkucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MzE4cHg7IHdpZHRoOjYyOXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkFzIGlucHV0LCB5b3UgYXJlIGdpdmVuIGEgKGNvbXBsZXRlIG9yIGluY29tcGxldGUpIG4gJnRpbWVzOyBuIGdyaWQgbWFkZSB3aXRoIG5vIG1vcmUgdGhhbiAybihuICsxKSBtYXRjaHN0aWNrcyBmb3IgYSBuYXR1cmFsIG51bWJlciBuICZsZTsgNSAuIFlvdXIgdGFzayBpcyB0byBjb21wdXRlIHRoZSBtaW5pbXVtIG51bWJlciBvZiBtYXRjaHN0aWNrcyB0YWtlbiBvdXQgdG8gZGVzdHJveSBhbGwgdGhlIHNxdWFyZXMgZXhpc3RpbmcgaW4gdGhlIGlucHV0IG4gJnRpbWVzOyBuIGdyaWQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29uc2lzdHMgb2YgVCB0ZXN0IGNhc2VzLiBUaGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMgKFQgKSBpcyBnaXZlbiBpbiB0aGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQgZmlsZS4gRWFjaCB0ZXN0IGNhc2UgY29uc2lzdHMgb2YgdHdvIGxpbmVzOiBUaGUgZmlyc3QgbGluZSBjb250YWlucyBhIG5hdHVyYWwgbnVtYmVyIG4gLCBub3QgZ3JlYXRlciB0aGFuIDUsIHdoaWNoIGltcGxpZXMgeW91IGFyZSBnaXZlbiBhIChjb21wbGV0ZSBvciBpbmNvbXBsZXRlKSBuICZ0aW1lczsgbiBncmlkIGFzIGlucHV0LCBhbmQgdGhlIHNlY29uZCBsaW5lIGJlZ2lucyB3aXRoIGEgbm9ubmVnYXRpdmUgaW50ZWdlciBrICwgdGhlIG51bWJlciBvZiBtYXRjaHN0aWNrcyB0aGF0IGFyZSBtaXNzaW5nIGZyb20gdGhlIGNvbXBsZXRlIG4gJnRpbWVzOyBuIGdyaWQsIGZvbGxvd2VkIGJ5IGsgbnVtYmVycyBzcGVjaWZ5aW5nIHRoZSBtYXRjaHN0aWNrcy4gTm90ZSB0aGF0IGlmIGsgaXMgZXF1YWwgdG8gemVybywgdGhlbiB0aGUgaW5wdXQgZ3JpZCBpcyBhIGNvbXBsZXRlIG4gJnRpbWVzOyBuIGdyaWQ7IG90aGVyd2lzZSwgdGhlIGlucHV0IGdyaWQgaXMgYW4gaW5jb21wbGV0ZSBuICZ0aW1lczsgbiBncmlkIHN1Y2ggdGhhdCB0aGUgc3BlY2lmaWVkIGsgbWF0Y2hzdGlja3MgYXJlIG1pc3NpbmcgZnJvbSB0aGUgY29tcGxldGUgbiAmdGltZXM7IG4gZ3JpZC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QcmludCBleGFjdGx5IG9uZSBsaW5lIGZvciBlYWNoIHRlc3QgY2FzZS4gVGhlIGxpbmUgc2hvdWxkIGNvbnRhaW4gdGhlIG1pbmltdW0gbnVtYmVyIG9mIG1hdGNoc3RpY2tzIHRoYXQgaGF2ZSB0byBiZSB0YWtlbiBvdXQgdG8gZGVzdHJveSBhbGwgdGhlIHNxdWFyZXMgaW4gdGhlIGlucHV0IGdyaWQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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

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