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

문제

상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다.

가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.

사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 보드의 크기 N이 주어진다. (3 ≤ N ≤ 50)

다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다. 빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 주어진다.

사탕의 색이 다른 인접한 두 칸이 존재하는 입력만 주어진다.

출력

첫째 줄에 상근이가 먹을 수 있는 사탕의 최대 개수를 출력한다.

예제 입력 1

3
CCP
CCP
PPC

예제 출력 1

3

예제 입력 2

4
PPPP
CYZY
CCPY
PPCC

예제 출력 2

4

예제 입력 3

5
YCPZY
CYZZP
CCPPP
YCYZC
CPPZZ

예제 출력 3

4

힌트

예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다.

W3sicHJvYmxlbV9pZCI6IjMwODUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYWNcdWQwZDUgXHVhYzhjXHVjNzg0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjNWI0XHViODM4XHVjNzQ0IFx1YzgwMVx1YzVkMCAmcXVvdDtcdWJkMDRcdWJjZjRcdWIyYzggKEJvbWJvbmkpJnF1b3Q7IFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWM5OTBcdWFjYThcdWQ1ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMFx1YzdhNSBcdWNjOThcdWM3NGNcdWM1ZDAgTiZ0aW1lcztOXHVkMDZjXHVhZTMwXHVjNWQwIFx1YzBhY1x1ZDBkNVx1Yzc0NCBcdWNjNDRcdWM2Y2MgXHViMTkzXHViMjk0XHViMmU0LiBcdWMwYWNcdWQwZDVcdWM3NTggXHVjMGM5XHVjNzQwIFx1YmFhOFx1YjQ1MCBcdWFjMTlcdWM5YzAgXHVjNTRhXHVjNzQ0IFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWMwYWNcdWQwZDVcdWM3NTggXHVjMGM5XHVjNzc0IFx1YjJlNFx1Yjk3OCBcdWM3NzhcdWM4MTFcdWQ1NWMgXHViNDUwIFx1Y2U3OFx1Yzc0NCBcdWFjZTBcdWI5NzhcdWIyZTQuIFx1YWRmOCBcdWIyZTRcdWM3NGMgXHVhY2UwXHViOTc4IFx1Y2U3OFx1YzVkMCBcdWI0ZTRcdWM1YjRcdWM3ODhcdWIyOTQgXHVjMGFjXHVkMGQ1XHVjNzQ0IFx1YzExY1x1Yjg1YyBcdWFkNTBcdWQ2NThcdWQ1NWNcdWIyZTQuJm5ic3A7XHVjNzc0XHVjODFjLCBcdWJhYThcdWI0NTAgXHVhYzE5XHVjNzQwIFx1YzBjOVx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWFlMzQgXHVjNWYwXHVjMThkIFx1YmQ4MFx1YmQ4NChcdWQ1ODkgXHViNjEwXHViMjk0IFx1YzVmNClcdWM3NDQgXHVhY2UwXHViOTc4IFx1YjJlNFx1Yzc0YyBcdWFkZjggXHVjMGFjXHVkMGQ1XHVjNzQ0IFx1YmFhOFx1YjQ1MCBcdWJhMzlcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBhY1x1ZDBkNVx1Yzc3NCBcdWNjNDRcdWM2Y2NcdWM5YzQgXHVjMGMxXHVkMGRjXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWJhMzlcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWMwYWNcdWQwZDVcdWM3NTggXHVjZDVjXHViMzAwIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViY2Y0XHViNGRjXHVjNzU4IFx1ZDA2Y1x1YWUzMCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDMgJmxlOyBOICZsZTsgNTApPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBOXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJjZjRcdWI0ZGNcdWM1ZDAgXHVjYzQ0XHVjNmNjXHVjODM4IFx1Yzc4OFx1YjI5NCBcdWMwYWNcdWQwZDVcdWM3NTggXHVjMGM5XHVjMGMxXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViZTY4XHVhYzA0XHVjMGM5XHVjNzQwIEMsIFx1ZDMwY1x1Yjc4MFx1YzBjOVx1Yzc0MCBQLCBcdWNkMDhcdWI4NWRcdWMwYzlcdWM3NDAgWiwgXHViMTc4XHViNzgwXHVjMGM5XHVjNzQwIFlcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYWNcdWQwZDVcdWM3NTggXHVjMGM5XHVjNzc0IFx1YjJlNFx1Yjk3OCBcdWM3NzhcdWM4MTFcdWQ1NWMgXHViNDUwIFx1Y2U3OFx1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NThcdWIyOTQgXHVjNzg1XHViODI1XHViOWNjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWJhMzlcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWMwYWNcdWQwZDVcdWM3NTggXHVjZDVjXHViMzAwIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1YzYwOFx1YzgxYyAzXHVjNzU4IFx1YWNiZFx1YzZiMCA0XHViYzg4IFx1ZDU4OVx1Yzc1OCBZXHVjNjQwIENcdWI5N2MgXHViYzE0XHVhZmI4XHViYTc0IFx1YzBhY1x1ZDBkNSBcdWIxMjQgXHVhYzFjXHViOTdjIFx1YmEzOVx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMzA4NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkJPTUJPTkkiLCJkZXNjcmlwdGlvbiI6IjxwPkxpdHRsZSBJdmFuIGlzIGJvcmVkIGF0IG1hdGggY2xhc3Mgc28gaGUgZGVjaWRlZCB0byBwbGF5IHBvcHVsYXIgZ2FtZSBjYWxsZWQgJnF1b3Q7Qm9tYm9uaSZxdW90Oy4gQXQgdGhlIGJlZ2lubmluZyBhbGwgZmllbGRzIG9mIE4mdGltZXM7TiBzcXVhcmUgYm9hcmQgY29udGFpbiBjYW5kaWVzIChub3QgbmVjZXNzYXJpbHkgb2Ygc2FtZSBjb2xvcikuIFdoZW4gaXRzIGhpcyB0dXJuIHBsYXllciBzaG91bGQgc3dhcCB0d28gbmVpZ2hib3VyaW5nICh1cCwgZG93biwgbGVmdCBvciByaWdodCkgY2FuZGllcyBvZiBkaWZmZXJlbnQgY29sb3IgYW5kIHRoZW4gcGljayBzb21lIHNlcXVlbmNlIChpbiByb3cgb3IgY29sdW1uKSBvZiBzYW1lIGNvbG9yIGNhbmRpZXMgd2hpY2ggaGUgd2lsbCB0YWtlIGFuZCBlYXQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkluaXRpYWwgYm9hcmQgY29uZmlndXJhdGlvbiBpcyBnaXZlbiwgaGVscCBJdmFuIGFuZCB3cml0ZSBhIHByb2dyYW0gd2hpY2ggd2lsbCBjYWxjdWxhdGUgbWF4aW1hbCBudW1iZXIgb2YgY2FuZGllcyBoZSBjYW4gd2luIGluIHRoZSBmaXJzdCBtb3ZlLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+SW4gdGhlIGZpcnN0IGxpbmUgb2Ygc3RhbmRhcmQgaW5wdXQgdGhlcmUgaXMgb25lIGludGVnZXIgTiAoMyAmbGU7IE4gJmxlOyA1MCksIGJvYXJkIGRpbWVuc2lvbnMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkluIG5leHQgTiBsaW5lcyBpbml0aWFsIGJvYXJkIGNvbmZpZ3VyYXRpb24gaXMgZ2l2ZW4sIGotdGggY2hhcmFjdGVyIGluIGktdGggcm93IGRlbm90ZXMgY29sb3Igb2YgY2FuZHkgYXQgc3F1YXJlIChpLCBqKSA6IEMgKHJlZCksIFAgKGJsdWUpLCBaIChncmVlbiksIFkgKHllbGxvdykuIEl0IHdpbGwgYWx3YXlzIGJlIHBvc3NpYmxlIHRvIG1ha2UgZmlyc3QgbW92ZS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5JbiB0aGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBzdGFuZGFyZCBvdXRwdXQgcHJpbnQgdGhlIG1heGltYWwgbnVtYmVyIG9mIGNhbmRpZXMgSXZhbiBjYW4gd2luIGluIHRoZSBmaXJzdCBtb3ZlLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiI8cD5TZWNvbmQgdGVzdCBleGFtcGxlIGV4cGxhbmF0aW9uOiBpbiBmaXJzdCByb3cgd2Ugc2VlIHNlcXVlbmNlIFBQUFAsIHNvIHN3YXBwaW5nIGFueSB0d28gY2FuZGllcyBpbiBvdGhlciByb3dzIGZpcnN0IHJvdyByZW1haW4gdW5jaGFuZ2VkIHNvIEl2YW4gY2FuIHRha2UgaXQuPFwvcD5cclxuXHJcbjxwPlRoaXJkIHRlc3QgZXhhbXBsZSBleHBsYW5hdGlvbjogc3dhcHBpbmcgY2FuZGllcyBZIGFuZCBDIGluIDR0aCByb3cgSXZhbiBnZXRzIHNlcXVlbmNlIENDQ0MgaW4gZmlyc3QgY29sdW1uLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2012 > Junior Croatian Olympiad in Informatics - Exam #1  1번

  • 데이터를 추가한 사람: 10jobss
  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: jh05013
  • 잘못된 조건을 찾은 사람: juhyun16