시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1039 196 168 22.340%

문제

테트리스는 아래와 같은 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+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNDkyMCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRoZSBHYW1lIG9mIFRldHJpcyIsImRlc2NyaXB0aW9uIjoiPHA+VGV0cmlzIGlzIGEgZmFtb3VzIHZpZGVvIGdhbWUgdGhhdCBoYXMgNSBwaWVjZXMgc2ltaWxhciB0byB0aGVzZTo8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC90ZXQzLnBuZ1wiIHN0eWxlPVwiZmxvYXQ6cmlnaHQ7IGhlaWdodDo0NzJweDsgd2lkdGg6MTI1cHhcIiBcLz5JbiB0aGlzIHByb2JsZW0sIHlvdSZyc3F1bztyZSBnaXZlbiBhbiBOeE4gZ3JpZCBvZiBpbnRlZ2Vycy4gV2Ugd2FudCB0byBwbGFjZSBhIHNpbmdsZSBwaWVjZSBvZiBUZXRyaXMgb24gdGhlIGdyaWQgc3VjaCB0aGF0IHRoZSBzdW0gb2YgdGhlIG51bWJlcnMgYmVsb3cgdGhlIHBpZWNlIGFyZSB0aGUgbWF4aW11bS4gTm90aWNlIHRoYXQgYWxsIGJ1dCB0aGUgbGFzdCBUZXRyaXMgcGllY2UgY2FuIGJlIHJvdGF0ZWQgYnkgOTAgZGVncmVlcy4gU29tZSBwaWVjZXMgZXZlbiBoYXZlIGZvdXIgZGlcdWZiMDBlcmVudCBvcmllbnRhdGlvbnMuIEFueSBvcmllbnRhdGlvbiBpcyBhY2NlcHRhYmxlIGFzIGxvbmcgYXMgdGhlIHBpZWNlIGNvbXBsZXRlbHkgXHVmYjAxdHMgaW5zaWRlIHRoZSBncmlkLiBGb3IgZXhhbXBsZSwgdGhlIGxlZnQtbW9zdCBwaWVjZSBjYW4gYmUgcGxhY2VkIG9uIHRoZSBcdWZiMDFyc3Qgcm93IG9mIHRoZSBncmlkLCB3aXRoIGEgc3VtIG9mIDgwLiBJdCBjYW4gYWxzbyBiZSBwbGFjZWQsIGZvciBleGFtcGxlLCBvbiB0aGUgdGhpcmQgY29sdW1uLCB5aWVsZGluZyBhIHN1bSBvZiA5MS4gQXMgYSBtYXR0ZXIgb2YgZmFjdCwgaW4gYSA0eDQgZ3JpZCwgd2UgY2FuIGhhdmUgNzcgZGlcdWZiMDBlcmVudCB3YXlzIHRvIHBsYWNlIHRoZSBUZXRyaXMgcGllY2VzLiBJbiB0aGUgc2FtcGxlIGdyaWQgc2hvd24gb24gdGhlIHJpZ2h0LCB0aGUgbGFyZ2VzdCBzdW0gdGhhdCBjYW4gYmUgYWNoaWV2ZWQgaXMgMTIwLjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCBkZXRlcm1pbmVzIHRoZSBsYXJnZXN0IHN1Y2ggc3VtIGZvciBhIGdpdmVuIGdyaWQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5Zb3VyIHByb2dyYW0gd2lsbCBiZSB0ZXN0ZWQgb24gb25lIG9yIG1vcmUgdGVzdCBjYXNlcy4gVGhlIFx1ZmIwMXJzdCBsaW5lIG9mIGEgdGVzdCBjYXNlIGhhcyBhIHNpbmdsZSBpbnRlZ2VyIE4gZGVub3RpbmcgdGhlIGdyaWQgc2l6ZSB3aGVyZSA0ICZsZTsgTiAmbGU7IDEwMC4gVGhlIGdyaWQgd2lsbCBiZSBzcGVjaVx1ZmIwMWVkIHVzaW5nIE4gbGluZXMgc3RhcnRpbmcgb24gdGhlIHNlY29uZCBsaW5lIGluIGEgcm93IG1ham9yIGZvcm1hdC4gRWFjaCBsaW5lIHdpbGwgaGF2ZSBOIGludGVnZXJzIHNlcGFyYXRlZCBieSBvbmUgb3IgbW9yZSBzcGFjZXMuIFRoZSBhYnNvbHV0ZSB2YWx1ZSBvZiBlYWNoIGludGVnZXIgaW4gdGhlIGdyaWQgd2lsbCBub3QgZXhjZWVkIDEsMDAwLDAwMC48XC9wPlxyXG5cclxuPHA+VGhlIGVuZCBvZiB0aGUgaW5wdXQgY2FzZXMgaXMgc3BlY2lcdWZiMDFlZCBieSBhIHplcm8gb24gYSBzZXBhcmF0ZSBsaW5lLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgb3V0cHV0IHRoZSByZXN1bHQgb24gYSBzaW5nbGUgbGluZSB1c2luZyB0aGUgZm9sbG93aW5nIGZvcm1hdDo8XC9wPlxyXG5cclxuPHByZT5cclxuay5yZXN1bHQ8XC9wcmU+XHJcblxyXG48cD5XaGVyZSBrIGlzIHRoZSB0ZXN0IGNhc2UgbnVtYmVyIChzdGFydGluZyBhdCAxLCkgYW5kIHJlc3VsdCBpcyB0aGUgbGFyZ2VzdCBzdW0gdGhhdCBjYW4gYmUgb2J0YWluZWQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

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

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