[백준 3085] 사탕게임 (C++)

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;
}