1. 입력
- 보드크기 n (3<= n <= 50)
- 빨간색 C, 파란색 P, 초록색 Z, 노란색 Y
2. 출력
- 먹을 수 있는 사탕의 최대 개수
3. 조건
- 사탕의 색이 다른 인접한 두 칸 골라서 교환하기
- 가장 긴 연속 부분 (행 또는 열)을 고른 다음 모두 먹기
4. 반례
5. 알고리즘
1) 색이 다른 인접한 두 칸 골라 바꾸기 -> 50*50*2
2) 행 또는 열 찾아서 사탕 먹기 -> 50*50
C++)
#include <iostream>
#include <algorithm>
#define MAX_NUM 52
using namespace std;
int n;
char arr[MAX_NUM][MAX_NUM];
char org[MAX_NUM][MAX_NUM];
int EatCandies() {
int tempCount = 1;
int maxCount = 0;
for (int i = 0; i < n; i++) {
char color = arr[i][0];
tempCount = 1;
// 행 비교
for (int j = 1; j < n; j++) {
if (arr[i][j] == color)
tempCount++;
else {
tempCount = 1;
color = arr[i][j];
}
maxCount = max(maxCount, tempCount);
}
// 열 비교
color = arr[0][i];
tempCount = 1;
for (int j = 1; j < n; j++) {
if (arr[j][i] == color)
tempCount++;
else {
tempCount = 1;
color = arr[j][i];
}
maxCount = max(maxCount, tempCount);
}
}
return maxCount;
}
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
cin >> org[i][j];
}
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n-1; j++) {
// 오른쪽 캔디와 비교
copy(&org[0][0], &org[0][0] + (MAX_NUM * MAX_NUM), &arr[0][0]);
if (arr[i][j] != arr[i][j + 1]) {
char temp = arr[i][j];
arr[i][j] = arr[i][j + 1];
arr[i][j + 1] = temp;
ans = max(ans, EatCandies());
}
// 아래쪽 캔디와 비교
if (i != n - 1) {
copy(&org[0][0], &org[0][0] + (MAX_NUM * MAX_NUM), &arr[0][0]);
if (arr[i][j] != arr[i + 1][j]) {
char temp = arr[i][j];
arr[i][j] = arr[i + 1][j];
arr[i + 1][j] = temp;
ans = max(ans, EatCandies());
}
}
}
}
cout << ans;
return 0;
}
'백준 2 > 완전탐색' 카테고리의 다른 글
| [백준 7568] 덩치 (0) | 2020.12.07 |
|---|---|
| [백준 1018] 체스판 칠하기 (C++/Python) (0) | 2020.12.07 |
| [백준 10448] 유레카 이론 (C++) (0) | 2020.12.07 |
| [백준 2231] 분해합 (C++/Python) (0) | 2020.12.07 |
| [백준 10971] 외판원 순회2 (0) | 2020.12.07 |