BOJ 3085 : 사탕게임 - C++

김정욱·2021년 2월 25일
0

Algorithm - 문제

목록 보기
121/249
post-thumbnail

사탕게임

코드


#include <iostream>
using namespace std;
char board[51][51];
int dx[2] = {0, 1};
int dy[2] = {1, 0};
int N;
void swap(pair<int,int> a, pair<int,int> b)
{
    char temp = board[a.first][a.second];
    board[a.first][a.second] = board[b.first][b.second];
    board[b.first][b.second] = temp;
}
int check(){
    int MAX=1;
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)
        {
            int rc=1,cc=1;
            char c1 = board[i][j];
            for(int r=i+1;r<N;r++)
            {
                if(board[r][j] == c1) rc++;
                else break;
            }
            for(int c=j+1;c<N;c++)
            {
                if(board[i][c] == c1) cc++;
                else break;
            }
            MAX = max(MAX, max(rc, cc));
        }
    }
    return MAX;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int ans = 1;
    cin >> N;
    for(int i=0;i<N;i++) cin >> board[i];
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)
        {
            for(int z=0;z<2;z++)
            {
                int ni = i + dy[z];
                int nj = j + dx[z];
                if(ni <0 or nj <0 or ni >=N or nj >=N) continue;
                swap({i,j}, {ni,nj});
                ans = max(ans, check());
                swap({i,j}, {ni,nj});
            }
        }
    }
    cout << ans;
    return 0;
}
  • 로직
    1) 오른쪽 칸 / 아래 칸 2개에 대해 현재 좌표와 board[][] 교환
    2) 바뀐 board[][] 에 대해 가장 긴 사탕 길이를 찾는다
    3) 1~2를 모든점에 대해 수행하며 MAX값 갱신
profile
Developer & PhotoGrapher

0개의 댓글