[BOJ] 3085번: 사탕 게임

문제 링크: 백준/BOJ https://www.acmicpc.net/problem/3085

3085번: 사탕 게임

 

 2주 전에 처음 풀었을 때는 무한 맞왜틀하다가 다시 풀어보니까 한번에 통과해서 기분 좋았던 문제다.

사실 생각을 할 것이 별로 없는 문제다. n이 최대 50이니 무식하게 완탐 돌려도 o(n^4)니까 제한 시간 안에 충분히 돈다.

사탕 교환은 인접한 서로 다른 사탕 2개에 한해서만 수행되므로 swap 후 먹을 수 있는 최대 사탕 개수 계산 후 다시 swap으로 되돌려야 한다는 점을 주의해줘야 한다. 또한 내가 맞왜틀했던 원인은 최대 사탕 개수는 교환이 이루어진 행과 열에서 나오지 않을 수도 있다는 점을 간과했기 때문이다.

 

/*
20200322
3085번 - 사탕 게임
*/
#include <iostream>
#include <string>
using namespace std;

char arr[50][50]; int ans = 1;
void func(int n) {
	char target; int sum = 1;
	//각각 행과 열 검사 - > o(n^2)
	for (int i = 0; i < n; ++i) {
		target = arr[i][0];
		sum = 1;
		for (int j = 1; j < n; ++j) {
			if (target == arr[i][j]) {
				sum++;
				if (ans < sum)
					ans = sum;
				continue;
			}
			target = arr[i][j];
			sum = 1;
		}
	}
	
	for (int i = 0; i < n; ++i) {
		target = arr[0][i];
		sum = 1;
		for (int j = 1; j < n; ++j) {
			if (target == arr[j][i]) {
				sum++;
				if (ans < sum)
					ans = sum;
				continue;
			}
			target = arr[j][i];
			sum = 1;
		}
	}
}

int main() {
	cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			cin >> arr[i][j];
		}
	}

	//o(n^2)만큼 사탕 교환함
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			if (i < n - 1 && arr[i][j] != arr[i + 1][j]) {
				swap(arr[i][j], arr[i + 1][j]);
				func(n);
				swap(arr[i][j], arr[i + 1][j]);
			}
			if (j < n - 1 && arr[i][j] != arr[i][j + 1]) {
				swap(arr[i][j], arr[i][j + 1]);
				func(n);
				swap(arr[i][j], arr[i][j + 1]);
			}
		}
	}

	cout << ans;
}