[BaekJoon/백준] 3085번 사탕 게임

정말 더 간단한 풀이는 없는 것인가 고민했는데, 찾아보니 없는 것 같다.

 

'스왑하고, 검사'하고 를 반복하면 된다.

 

총 O(N^4) 정도 나오겠다. N이 50이니까 1초안에 해결은 된다.

(간단한 연산을 컴퓨터는 1초에 1억번)

 

#include <iostream>
#include <algorithm>

using namespace std;

int N;
char MAP[50][50];

int MAX;

// 시간복잡도 O(n^2)
void EVALUATE() {
    
    int COUNT = 0;
    
    // 행마다 검사
    for(int i = 0; i < N; i++) {
        
        COUNT = 0;
        for(int j = 1; j < N; j++) {
            
            if(MAP[i][j] == MAP[i][j - 1])
                COUNT++;
            else
                COUNT = 0;
            
            if(MAX < COUNT)
                MAX = COUNT;
            
        }
        
    }
    
    // 열마다 검사
    for(int i = 0; i < N; i++) {
        
        COUNT = 0;

        for(int j = 1; j < N; j++) {
            
            if(MAP[j][i] == MAP[j - 1][i])
                COUNT++;
            else
                COUNT = 0;
            
            if(MAX < COUNT)
                MAX = COUNT;
            
        }
        
    }

}


int main() {
    
    cin >> N;
    
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            cin >> MAP[i][j];
        }
    }
    
    
    EVALUATE();
    
    
    for(int i = 0; i < N; i++) {
        
        for(int j = 0; j < N; j++) {
            
            // 범위를 벗어나지 않는다면, 오른쪽 체크
            if(j + 1 < N && MAP[i][j] != MAP[i][j + 1]) {
                
                swap(MAP[i][j], MAP[i][j + 1]);
                EVALUATE(); // 더 줄이려면, 전체가 아니라 바꾼 부분만 평가하는 함수를 따로 만들어도 된다.
                swap(MAP[i][j], MAP[i][j + 1]);
                
            }
            
            // 범위를 벗어나지 않는다면, 아래쪽 체크
            if(i + 1 < N && MAP[i][j] != MAP[i + 1][j]) {
                
                swap(MAP[i][j], MAP[i + 1][j]);
                EVALUATE(); // 더 줄이려면, 전체가 아니라 바꾼 부분만 평가하는 함수를 따로 만들어도 된다.
                swap(MAP[i][j], MAP[i + 1][j]);

                
            }
            
            
        }
    }
    
    // 들어있는 값은 1을 더해줘야 하는 값으로 계산한 값이다.
    cout << MAX + 1 << "\n";
    
}

 

 

소요 시간 : 30분