https://www.acmicpc.net/problem/3085
문제의 예시를 보자
3
CCP
CCP
PPC
이것에 대한 답은 3이다
왜냐하면
앞선 사진과 같이 2행 3열 P와 3행 3열 p를 바꾸게 되면
CCP
CCC
PPP
이렇게
한줄에 최대 3개를 먹을 수 있게 되기 때문이다.
문제만 보기에는 아마 헷갈릴 부분이 있을것인데
교환은 단 "한번"만 이루어 진다.
이 내용은 문제에 나와있지 않고 질문 게시판에서 찾았다.. 이것때문에 초반 생각이 좀 힘들었다.
쨋든, 배열의 최대 크기는 50이고 1초나 주면
모든 경우의 수를 보기에는 충분 할 것이다.
즉 브루트 포스로 봐보자
먼저, 문제에 정확히 명시되어 있지 않으므로 초기 상태에 대한 최대 먹을 수 있는 캔디의 수를 구하자!
먹을 수 있는 캔디의 수를 구하는 것은 앞서말한 모든 경우의 수를 보면 된다
1. 몇행인지 고정시킨 후 연속된 수를 구하기
2. 몇열인지 고정시킨 후 연속된 수를 구하기
그것을 대충 코드로 써보자
// 가로 확인
for (int i = 0; i < n; i++)
{
int temp_max = 1;
int temp = 1;
for (int j = 1; j < n; j++)
{
if (arr[i][j] == arr[i][j - 1])
{
temp_max++;
}
else
{
temp = max(temp, temp_max);
temp_max = 1;
}
}
temp_max = max(temp_max, temp);
max_candy = max(max_candy, temp_max);
}
// 세로 확인
for (int i = 0; i < n; i++)
{
int temp_max = 1;
int temp = 1;
for (int j = 1; j < n; j++)
{
if (arr[j][i] == arr[j - 1][i])
{
temp_max++;
}
else
{
temp = max(temp, temp_max);
temp_max = 1;
}
}
temp_max = max(temp_max, temp);
max_candy = max(max_candy, temp_max);
}
코드만 보면 temp와 temp_max는 무엇인고 할 것이다.
먼저 temp_max는 이해가 쉬울 것이다.
바로, 해당 (행,열)에서 선택된 가장 긴 연속된 사탕의 수이다.
그래서 해당 (행,열)로 들어가기 전(2번째 for문) temp_max=1로 해놓고(시작은 1이니까) 이전값과 현재값을 비교시켜가면서 temp_max를 더해준다
else인 경우는 만약 cccpcc라는사탕이 놓여져있으면 temp_max가 네번째에서 1이되고, 이후 행이끝나면 뒤에있는 cc두개만 봐서 2가 될 것이다.
그래서 temp를 통해서 이전 수 중 가장 큰 값을 저장시켜 놓는 것이다
이후 max 함수를통해 저장시켜 놓는 것이다.
그렇다면 비교하는 코드는 만들어 놓았으니, 이제 바꾸는 경우에 대해 생각해보자
이것도 간단하다.
1.고정한 행,렬을 기준으로 현재값 현재+1값을 바꿔준다
2.그 행렬을 다시 위에서 말한 코드로 검사한다
3.바꾼 행,렬을 다시 원상태로 바꿔준다
4.모든 행,렬에 대해 검사하면 끝
코드로써보겠다
#include <iostream>
#include <algorithm>
using namespace std;
int checkMaxCandies(string arr[], int n, int max_candy)
{
// 가로 확인
for (int i = 0; i < n; i++)
{
int temp_max = 1;
int temp = 1;
for (int j = 1; j < n; j++)
{
if (arr[i][j] == arr[i][j - 1])
{
temp_max++;
}
else
{
temp = max(temp, temp_max);
temp_max = 1;
}
}
temp_max = max(temp_max, temp);
max_candy = max(max_candy, temp_max);
}
// 세로 확인
for (int i = 0; i < n; i++)
{
int temp_max = 1;
int temp = 1;
for (int j = 1; j < n; j++)
{
if (arr[j][i] == arr[j - 1][i])
{
temp_max++;
}
else
{
temp = max(temp, temp_max);
temp_max = 1;
}
}
temp_max = max(temp_max, temp);
max_candy = max(max_candy, temp_max);
}
return max_candy;
}
int main()
{
int n;
cin >> n;
string arr[n];
for (int i = 0; i < n; i++)
cin >> arr[i];
int max_candy = checkMaxCandies(arr, n, 1);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n - 1; j++)
{
swap(arr[i][j], arr[i][j + 1]);
max_candy = max(max_candy, checkMaxCandies(arr, n, max_candy));
// cout << i << " " << j << "<<i와 j 2 : " << max_candy << "\n";
swap(arr[i][j], arr[i][j + 1]);
swap(arr[j][i], arr[j + 1][i]);
max_candy = max(max_candy, checkMaxCandies(arr, n, max_candy));
// cout << i << " " << j << "<<i와 j 3 : " << max_candy << "\n";
swap(arr[j][i], arr[j + 1][i]);
}
}
cout << max_candy;
return 0;
}
swap이란 함수를 사용하여 문자열을 바꾸었다.