3085번: 사탕 게임
문제 상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다. 가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다. 사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하
www.acmicpc.net
바꾸지 않은 상태에서 먹을 수 있는 최대 사탕갯수를 먼저 구한 다음, 보드의 0,0좌표를 시작으로 스왑하는 모든 경우의 수에 대하여 최댓값을 갱신해주면 된다.
왼쪽위에서부터 차례대로 스왑을 진행하기 때문에 한 칸에서 상하좌우 모든 방향으로 스왑하는 경우를 계산할 필요 없이 왼쪽과 아랫쪽 사탕과 스왑하는 경우만 계산해줘도 모든 경우를 확인할 수 있다.
추가로 구한 사탕 개수가 보드의 행 길이와 같다면 그 값보다 큰 값이 나올 수 없으므로 함수를 리턴하는 조건을 달아주었다.
|
#include <iostream>
#include <string>
#include <vector>
using namespace std;
vector<string> board;
int maxLen, candyMax = 1;
inline int max(int a, int b) { return a > b ? a : b; }
void FindCandyMax()
{
for (int i = 0; i < maxLen; i++)
{
for (int j = 0; j < maxLen; j++)
{
int temp = j, colCandyCnt = 1, rowCandyCnt = 1;
bool colCandy = true, rowCandy = true;
while (++temp < maxLen)
{
if (colCandy && board[j][i] != board[temp][i])
colCandy = false;
if (rowCandy && board[i][j] != board[i][temp])
rowCandy = false;
if (!colCandy && !rowCandy) break;
if (colCandy) colCandyCnt++;
if (rowCandy) rowCandyCnt++;
}
candyMax = max(candyMax, max(colCandyCnt, rowCandyCnt));
}
}
}
void CandySwap(int col, int row)
{
char temp = board[col][row];
if (row + 1 < maxLen)
{
board[col][row] = board[col][row + 1];
board[col][row + 1] = temp;
FindCandyMax();
board[col][row + 1] = board[col][row];
board[col][row] = temp;
}
if (col + 1 < maxLen)
{
board[col][row] = board[col + 1][row];
board[col + 1][row] = temp;
FindCandyMax();
board[col + 1][row] = board[col][row];
board[col][row] = temp;
}
}
void Solution()
{
FindCandyMax();
if (candyMax == maxLen) return;
for(int i=0; i<maxLen; i++)
for (int j = 0; j < maxLen; j++)
{
CandySwap(i, j);
if (candyMax == maxLen) return;
}
}
int main(void)
{
cin >> maxLen;
for(int i=0; i<maxLen; i++)
{
string str;
cin >> str;
board.push_back(str);
}
Solution();
cout << candyMax << endl;
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
|
알고리즘 200일 프로젝트 - 19day
내일도 열심히!
'알고리즘 > BOJ' 카테고리의 다른 글
| 백준 1038번: 감소하는 수 (0) | 2020.04.25 |
|---|---|
| 백준 1051번 : 숫자 정사각형 (0) | 2020.04.24 |
| 백준 2503번: 숫자 야구 (c++) (0) | 2020.04.23 |
| 백준 15684번: 사다리 조작 (c++) (0) | 2020.04.22 |
| 백준 10448: 유레카 이론 (c++) (0) | 2020.04.21 |