3085 사탕게임

https://www.acmicpc.net/problem/3085

3085번: 사탕 게임

사탕 게임 성공

한국어   

시간 제한메모리 제한제출정답맞은 사람정답 비율

1 초

128 MB

8157

2559

1926

31.399%

문제

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

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

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

입력

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

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

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

출력

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

예제 입력 1 복사

5 YCPZY CYZZP CCPPP YCYZC CPPZZ

예제 출력 1 복사

4

 

힌트

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

출처

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

 

<개인풀이>

 

1.문제 조건을 보면, 사탕의 색이 다른 인접한 두칸을 고른다음,

사탕을 서로 교환한다. 

(인접한 두 칸은, 서로 가로행, 세로열 자리를 바꾸는것을 힌트를 보고 알았다)

 

2. 사탕의 자리를 교체한뒤 부분 행, 열을 파악한다.

 

3. 자리를 행끼리 또는 열끼리 바꾼 다음, 바뀐 배열에서 사탕을

 (1) 가로로 연속된 갯수가 많은지

 (2) 세로로 연속된 갯수가 많은지 

파악한다.

 

4. 행 교환을 하고, 위 (1)번 그 다음 (2) 수행해서 가장 많은 값을 저장,
   

5. 열 교환을 하고, 위(1)번 그 다음 (2) 수행을 해서 가장 많은 값을 저장

을 생각해보면

행 끼리 교환후, 다시 처음 위치로 바꿔준다. 그 후에 다시

열 끼리 교환후, 다시 처음 위치로 바꿔주고.

 

(1)행 교환 -> 3번의 (1)(2) 를 수행한다음 나온 최대값, A
(2)원위치로 돌리고

(3)열 교환 -> 3번의 (1)(2) 를 수행한다음 나온 최대값, B

 

A와 B중 가장 큰값을 찾는것.

 

#include<iostream>
#include<algorithm>
char mat[50][50];
using namespace std;

int bfc(void);
int n;
int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);


	cin >> n;

	for (unsigned short i = 0; i < n; ++i)
	{
		for (unsigned short k = 0; k < n; ++k)
		{
			cin >> mat[i][k];
		}
	}

	int ans = 0;
	for (unsigned short i = 0; i < n; ++i)
	{
		int result = 0;
		for (unsigned short k = 0; k < n-1; ++k)
		{
			//사탕 가로 바꾸고
			swap(mat[i][k], mat[i][k + 1]);
			//비교 
			result = bfc();
			swap(mat[i][k], mat[i][k + 1]);
			if (ans < result) ans = result;
			
			//사탕 세로 바꾸고
			swap(mat[k][i], mat[k+1][i]);
			result = bfc();
			swap(mat[k][i], mat[k + 1][i]);
			if (ans < result) ans = result;

			
		}
	}
	printf("%d\n", ans);
	return 0;
}
int bfc()
{
	int count = 1;
	int r=0, b=0;
	for (int i = 0; i < n; ++i) //가로 검사
	{
		count = 1;
		for (unsigned short k = 0; k < n-1; ++k)
		{
			if (mat[i][k] == mat[i][k + 1])
			{
				count += 1;
			}
			else count = 1;
			if (r < count) r = count;
		}
	}

	count = 1;
	for (int i = 0; i < n; ++i) //세로 검사
	{
		count = 1;
		for (unsigned short k = 0; k < n - 1; ++k)
		{
			if (mat[k][i] == mat[k+1][i])
			{
				count += 1;
			}
			else count = 1;
			if (r < count) r = count;
		}
	}

	return r;
}