[C++] BOJ 3085 사탕게임

👉백준 3085 사탕게임

🤔😮 문제 해결 방법

• N의 크기가 50이하이므로 모든 경우를 해도 시간초과가 나지 않는다

  따라서, 모든 배열의 원소를 바꿔가면서 연속으로 먹을 수 있는 사탕의 최대 갯수를 구해보았다.

✨ 1. 모든 경우의 수를 수행함으로써 문제해결

50x50이 넘는 크기를 가진 arr 이차원 배열을 모두 탐색하면서 우측 열의 원소와 교환, 아래쪽 행의 원소와의 교환을 반복하며 최댓값을 갱신해나간다. 최댓값을 구하는 함수는 따로 분리해서 작성해주었다. 연속된 부분이기에 다른 원소를 만나면 갯수를 다시 1로 갱신해주었다.

#include <iostream>
#include <algorithm>
using namespace std;

char arr[60][60];

int maximum=0;
int n;

void findMaximum(){
    char a; char b;
    
    for(int i=0; i<n; i++){
        int rowcnt=1;
        a=arr[i][0];
        
        for(int j=1; j<n; j++){
            if(arr[i][j]==a) rowcnt++;
            else rowcnt=1;
            
            a=arr[i][j];
            b=arr[j][i];
            
            if(rowcnt>maximum) maximum=rowcnt;
        }
    }
    
    for(int j=0; j<n; j++){
        int colcnt=1;
        b=arr[0][j];
        
        for(int i=1; i<n; i++){
            if(arr[i][j]==b) colcnt++;
            else colcnt=1;
            
            b=arr[i][j];
            
            if(colcnt>maximum) maximum=colcnt;
        }
    }
    
}

int main(){
    cin>>n;
    
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin>>arr[i][j];
        }
    }
    
    for(int i=0; i<n; i++){
        for(int j=0; j<n-1; j++){
            swap(arr[i][j], arr[i][j+1]);
            findMaximum();
            swap(arr[i][j], arr[i][j+1]);
        }
    }
    
    for(int i=0; i<n; i++){
        for(int j=0; j<n-1; j++){
            swap(arr[j][i], arr[j+1][i]);
            findMaximum();
            swap(arr[j][i], arr[j+1][i]);
        }
    }
    
    cout<<maximum;
    return 0;
}