시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB215945933621.734%

문제

테트리스는 아래와 같은 5가지 조각으로 이루어져 있다.

정수로 이루어진 N×N 표가 주어진다. 테트리스 블록 중 하나를 표에 놓아 블록 아래에 있는 숫자의 합의 최댓값을 구하는 프로그램을 작성하시오.

모든 테트리스 블록은 90도씩 회전시킬 수 있다. 일부 조각은 총 4가지 형태를 가질 수 있다. 블록이 모두 표 안에 들어있는 형태는 모두 가능한 형태이다.

예를 들어, 가장 왼쪽 블록을 첫 행에 놓으면 합 80을 얻을 수 있다. 90도 회전시켜 셋째 열에 놓으면 91을 얻을 수 있다.

표의 크기가 4×4인 경우에 블록을 놓는 방법의 수는 총 77가지이다. 위의 예제에서 가장 큰 합은 120이다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 표의 크기 N이 주어지고, 4 ≤ N ≤ 100을 만족한다. 둘째 줄부터 표에 쓰여 있는 숫자가 주어진다. 숫자는 절댓값이 1,000,000을 넘지 않는 정수이다.

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스 마다, 케이스 번호를 출력하고 가장 큰 합을 출력한다.

예제 입력 1

4 
70  2  1 7
 7  1 30 6 
 4 30 30 5 
 3  1 30 2 
0

예제 출력 1

1. 120
W3sicHJvYmxlbV9pZCI6IjQ5MjAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQxNGNcdWQyYjhcdWI5YWNcdWMyYTQgXHVhYzhjXHVjNzg0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWQxNGNcdWQyYjhcdWI5YWNcdWMyYTRcdWIyOTQgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1Yzc0MCA1XHVhYzAwXHVjOWMwIFx1Yzg3MFx1YWMwMVx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3RldC5wbmdcIiBzdHlsZT1cImhlaWdodDo1NnB4OyB3aWR0aDozNDNweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWM4MTVcdWMyMThcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IE4mdGltZXM7TiBcdWQ0NWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWQxNGNcdWQyYjhcdWI5YWNcdWMyYTQgXHViZTE0XHViODVkIFx1YzkxMSBcdWQ1NThcdWIwOThcdWI5N2MgXHVkNDVjXHVjNWQwIFx1YjE5M1x1YzU0NCBcdWJlMTRcdWI4NWQgXHVjNTQ0XHViNzk4XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWMyMmJcdWM3OTBcdWM3NTggXHVkNTY5XHVjNzU4IFx1Y2Q1Y1x1YjMxM1x1YWMxMlx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHA+XHViYWE4XHViNGUwIFx1ZDE0Y1x1ZDJiOFx1YjlhY1x1YzJhNCBcdWJlMTRcdWI4NWRcdWM3NDAgOTBcdWIzYzRcdWM1MjkgXHVkNjhjXHVjODA0XHVjMmRjXHVkMGFjIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Yzc3Y1x1YmQ4MCBcdWM4NzBcdWFjMDFcdWM3NDAgXHVjZDFkIDRcdWFjMDBcdWM5YzAgXHVkNjE1XHVkMGRjXHViOTdjIFx1YWMwMFx1YzljOCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWJlMTRcdWI4NWRcdWM3NzQgXHViYWE4XHViNDUwIFx1ZDQ1YyBcdWM1NDhcdWM1ZDAgXHViNGU0XHVjNWI0XHVjNzg4XHViMjk0IFx1ZDYxNVx1ZDBkY1x1YjI5NCBcdWJhYThcdWI0NTAgXHVhYzAwXHViMmE1XHVkNTVjIFx1ZDYxNVx1ZDBkY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC90ZXQyKDEpLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjExNnB4OyB3aWR0aDo0NzZweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWFjMDBcdWM3YTUgXHVjNjdjXHVjYWJkIFx1YmUxNFx1Yjg1ZFx1Yzc0NCBcdWNjYWIgXHVkNTg5XHVjNWQwIFx1YjE5M1x1YzczY1x1YmE3NCBcdWQ1NjkgODBcdWM3NDQgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIDkwXHViM2M0IFx1ZDY4Y1x1YzgwNFx1YzJkY1x1Y2YxYyBcdWMxNGJcdWM5ZjggXHVjNWY0XHVjNWQwIFx1YjE5M1x1YzczY1x1YmE3NCA5MVx1Yzc0NCBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNDVjXHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YWMwMCA0JnRpbWVzOzRcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwIFx1YmUxNFx1Yjg1ZFx1Yzc0NCBcdWIxOTNcdWIyOTQgXHViYzI5XHViYzk1XHVjNzU4IFx1YzIxOFx1YjI5NCBcdWNkMWQgNzdcdWFjMDBcdWM5YzBcdWM3NzRcdWIyZTQuIFx1YzcwNFx1Yzc1OCBcdWM2MDhcdWM4MWNcdWM1ZDBcdWMxMWMgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWQ1NjlcdWM3NDAgMTIwXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDQ1Y1x1Yzc1OCBcdWQwNmNcdWFlMzAgTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWFjZTAsIDQgJmxlOyBOICZsZTsgMTAwXHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1Y1x1YjJlNC4gXHViNDU4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBcdWQ0NWNcdWM1ZDAgXHVjNGYwXHVjNWVjIFx1Yzc4OFx1YjI5NCBcdWMyMmJcdWM3OTBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWMyMmJcdWM3OTBcdWIyOTQgXHVjODA4XHViMzEzXHVhYzEyXHVjNzc0IDEsMDAwLDAwMFx1Yzc0NCBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0IFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgMFx1Yzc3NCBcdWQ1NThcdWIwOTggXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0IFx1YjljOFx1YjJlNCwgXHVjZjAwXHVjNzc0XHVjMmE0IFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWFjZTAgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWQ1NjlcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjQ5MjAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUaGUgR2FtZSBvZiBUZXRyaXMiLCJkZXNjcmlwdGlvbiI6IjxwPlRldHJpcyBpcyBhIGZhbW91cyB2aWRlbyBnYW1lIHRoYXQgaGFzIDUgcGllY2VzIHNpbWlsYXIgdG8gdGhlc2U6PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvdGV0My5wbmdcIiBzdHlsZT1cImZsb2F0OnJpZ2h0OyBoZWlnaHQ6NDcycHg7IHdpZHRoOjEyNXB4XCIgXC8+SW4gdGhpcyBwcm9ibGVtLCB5b3UmcnNxdW87cmUgZ2l2ZW4gYW4gTnhOIGdyaWQgb2YgaW50ZWdlcnMuIFdlIHdhbnQgdG8gcGxhY2UgYSBzaW5nbGUgcGllY2Ugb2YgVGV0cmlzIG9uIHRoZSBncmlkIHN1Y2ggdGhhdCB0aGUgc3VtIG9mIHRoZSBudW1iZXJzIGJlbG93IHRoZSBwaWVjZSBhcmUgdGhlIG1heGltdW0uIE5vdGljZSB0aGF0IGFsbCBidXQgdGhlIGxhc3QgVGV0cmlzIHBpZWNlIGNhbiBiZSByb3RhdGVkIGJ5IDkwIGRlZ3JlZXMuIFNvbWUgcGllY2VzIGV2ZW4gaGF2ZSBmb3VyIGRpXHVmYjAwZXJlbnQgb3JpZW50YXRpb25zLiBBbnkgb3JpZW50YXRpb24gaXMgYWNjZXB0YWJsZSBhcyBsb25nIGFzIHRoZSBwaWVjZSBjb21wbGV0ZWx5IFx1ZmIwMXRzIGluc2lkZSB0aGUgZ3JpZC4gRm9yIGV4YW1wbGUsIHRoZSBsZWZ0LW1vc3QgcGllY2UgY2FuIGJlIHBsYWNlZCBvbiB0aGUgXHVmYjAxcnN0IHJvdyBvZiB0aGUgZ3JpZCwgd2l0aCBhIHN1bSBvZiA4MC4gSXQgY2FuIGFsc28gYmUgcGxhY2VkLCBmb3IgZXhhbXBsZSwgb24gdGhlIHRoaXJkIGNvbHVtbiwgeWllbGRpbmcgYSBzdW0gb2YgOTEuIEFzIGEgbWF0dGVyIG9mIGZhY3QsIGluIGEgNHg0IGdyaWQsIHdlIGNhbiBoYXZlIDc3IGRpXHVmYjAwZXJlbnQgd2F5cyB0byBwbGFjZSB0aGUgVGV0cmlzIHBpZWNlcy4gSW4gdGhlIHNhbXBsZSBncmlkIHNob3duIG9uIHRoZSByaWdodCwgdGhlIGxhcmdlc3Qgc3VtIHRoYXQgY2FuIGJlIGFjaGlldmVkIGlzIDEyMC48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgZGV0ZXJtaW5lcyB0aGUgbGFyZ2VzdCBzdWNoIHN1bSBmb3IgYSBnaXZlbiBncmlkLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIHdpbGwgYmUgdGVzdGVkIG9uIG9uZSBvciBtb3JlIHRlc3QgY2FzZXMuIFRoZSBcdWZiMDFyc3QgbGluZSBvZiBhIHRlc3QgY2FzZSBoYXMgYSBzaW5nbGUgaW50ZWdlciBOIGRlbm90aW5nIHRoZSBncmlkIHNpemUgd2hlcmUgNCAmbGU7IE4gJmxlOyAxMDAuIFRoZSBncmlkIHdpbGwgYmUgc3BlY2lcdWZiMDFlZCB1c2luZyBOIGxpbmVzIHN0YXJ0aW5nIG9uIHRoZSBzZWNvbmQgbGluZSBpbiBhIHJvdyBtYWpvciBmb3JtYXQuIEVhY2ggbGluZSB3aWxsIGhhdmUgTiBpbnRlZ2VycyBzZXBhcmF0ZWQgYnkgb25lIG9yIG1vcmUgc3BhY2VzLiBUaGUgYWJzb2x1dGUgdmFsdWUgb2YgZWFjaCBpbnRlZ2VyIGluIHRoZSBncmlkIHdpbGwgbm90IGV4Y2VlZCAxLDAwMCwwMDAuPFwvcD5cclxuXHJcbjxwPlRoZSBlbmQgb2YgdGhlIGlucHV0IGNhc2VzIGlzIHNwZWNpXHVmYjAxZWQgYnkgYSB6ZXJvIG9uIGEgc2VwYXJhdGUgbGluZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIG91dHB1dCB0aGUgcmVzdWx0IG9uIGEgc2luZ2xlIGxpbmUgdXNpbmcgdGhlIGZvbGxvd2luZyBmb3JtYXQ6PFwvcD5cclxuXHJcbjxwcmU+XHJcbmsucmVzdWx0PFwvcHJlPlxyXG5cclxuPHA+V2hlcmUgayBpcyB0aGUgdGVzdCBjYXNlIG51bWJlciAoc3RhcnRpbmcgYXQgMSwpIGFuZCByZXN1bHQgaXMgdGhlIGxhcmdlc3Qgc3VtIHRoYXQgY2FuIGJlIG9idGFpbmVkLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

ICPC > Regionals > Africa and Arab > Arab Collegiate Programming Contest > 2006 Arab Collegiate Programming Contest B번

  • 문제를 번역한 사람: baekjoon
  • 잘못된 조건을 찾은 사람: cubalys
  • 문제의 오타를 찾은 사람: doju