[BOJ] 3085번 사탕 게임

BOJ 3085번 사탕 게임

• 브루투포스

이게 가능한 풀이인건가. 3<=N<=50인 이유가 있었다고 생각한다. 더 커지면 1초 시간 제한 바로 넘어가겠지

하나씩 바꾼 후 k에 따라서 전체 탐색을 했다.
k가 1부터 N까지 반복될 동안 i는 k행에서 모든 원소, k열에서 모든 원소를 각각 탐색하며 각 행/열에서 연속으로 가장 많이 나온 사탕의 개수를 계산하여 그 중 큰 값을 골랐다.

내가 조금 방식했던 반례는

4
CCCP
CCCP
CCCP
CCCP

이다.

앞 원소와 현재 원소가 같지 않을 때만 max를 계산하게 해서 이 반례에서 틀렸었다.

완전 탐색이다 보니 풀이는 모두 비슷비슷한 듯

풀이

#include <iostream>
using namespace std;

char bomboni[52][52];
int N, answer;

// 좌, 하
int dx[4] = {0, 1};
int dy[4] = {1, 0};

void swap(int x, int y, int x_, int y_){
  char tmp = bomboni[x][y];
  bomboni[x][y] = bomboni[x_][y_];
  bomboni[x_][y_] = tmp;
}

void checkBomboni(){
  char curCandy[2];
  int curCnt[2], curMax[2]; // {행, 열}
  int result;

  for(int k=1;k<=N;k++){
    for(int i=0;i<2;i++){
      curCnt[i] = 1;
      curMax[i] = 1;
    }

    curCandy[0] = bomboni[k][1];
    for(int i=1;i<N;i++){
      // 행 기준
      if(curCandy[0] == bomboni[k][i+1]) curCnt[0]++;
      else {
        if(curMax[0] < curCnt[0]) curMax[0] = curCnt[0];
        curCandy[0] = bomboni[k][i+1];
        curCnt[0] = 1;
      }
    }
    if(curMax[0] < curCnt[0]) curMax[0] = curCnt[0];

    curCandy[1] = bomboni[1][k];
    for(int i=1;i<N;i++){
      // 열 기준
      if(curCandy[1] == bomboni[i+1][k]) curCnt[1]++;
      else {
        if(curMax[1] < curCnt[1]) curMax[1] = curCnt[1];
        curCandy[1] = bomboni[i+1][k];
        curCnt[1] = 1;
      }
    }
    if(curMax[1] < curCnt[1]) curMax[1] = curCnt[1];
    
    result = curMax[0] > curMax[1] ? curMax[0] : curMax[1];
    if(result > answer) answer = result;
  }
}

int main() {
  cin>>N;
  
  for(int i=1;i<=N;i++){
    for(int j=1;j<=N;j++){
      cin>>bomboni[i][j];
    }
  }
  
  for(int i=1;i<=N;i++){
    for(int j=1;j<=N;j++){
      for(int k=0;k<2;k++){
        if(bomboni[i][j] == bomboni[i+dx[k]][j+dy[k]]) continue;

        swap(i, j, i+dx[k], j+dy[k]);
        checkBomboni();
        swap(i, j, i+dx[k], j+dy[k]);
      }
    }
  }

  cout<<answer;
}

시간복잡도

O(N^4) 실화?