백준 3085 - 사탕 게임

https://www.acmicpc.net/problem/3085

3085번: 사탕 게임

문제 설명

---

가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 사탕의 색이 다른 인접한 두 칸을 고른다.

그 다음 고른 칸의 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분을 고른 다음 모두 먹는다.

사탕이 채워진 상태가 주어졌을 때, 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.

 

 

접근 방법

---

 

1. 양 옆을 바꾸고 제일 길게 먹을 수 있는 사탕의 길이를 파악합니다.

i) 가로로 제일 긴 사탕, ii) 세로로 제일 긴 사탕

그 중 긴 사탕의 길이를 선택합니다.

 

2. 위 아래를 바꾸고 제일 길게 먹을 수 있는 사탕의 길이를 파악합니다.

i) 가로로 제일 긴 사탕, ii) 세로로 제일 긴 사탕

마찬가지로 그 중 긴 사탕의 길이를 선택합니다.

 

3. 1과 2에서 구한 길이 중 더 긴 값을 출력합니다.

 

 

코드 

---

#include <iostream>
#include <vector>
#include<algorithm>
using namespace std;
int n, Max=0;
char arr[51][51];

void hori(){
    for (int i = 0; i < n; i++) {
        int cnt = 1;
        for (int j = 0; j < n; j++) { // chk 가로
            if (arr[i][j] == arr[i][j + 1]) { cnt++; }
            else{
                if (Max < cnt)
                    Max = cnt;
                cnt = 1;
            }
        }
    }

}
 void verti(){
     for (int i = 0; i < n; i++) {
         int cnt = 1;
         for (int j = 0; j < n; j++) { // chk 세로
             if (arr[j][i] == arr[j + 1][i]) {cnt++; }
             else {
                 if (Max < cnt)
                     Max = cnt;
                 cnt = 1;
             }
         }
     }
}
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++) {
            char tmp = arr[i][j];
            arr[i][j] = arr[i][j + 1];
            arr[i][j + 1] = tmp;
            hori();
            verti();
            tmp = arr[i][j];
            arr[i][j] = arr[i][j + 1];
            arr[i][j + 1] = tmp;
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n-1; j++) {
            char tmp = arr[j][i];
            arr[j][i] = arr[j+1][i];
            arr[j+1][i] = tmp;
            hori();
            verti();
            tmp = arr[j][i];
            arr[j][i] = arr[j + 1][i];
            arr[j + 1][i] = tmp;
        }
    }

    cout << Max << '\n';
    return 0;

}

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
 
const int MAX = 50;
 
int N;
string board[MAX];
 
int numOfCandy()
{
        int result = 1;
        //양 옆
        for (int i = 0; i < N; i++)
        {
                 int temp = 1;
                 for (int j = 1; j < N; j++)
                         if (board[i][j - 1] == board[i][j])
                                 temp++;
                         else
                         {
                                 result = max(result, temp);
                                 temp = 1;
                         }
                 result = max(result, temp);
        }
        //위 아래
        for (int i = 0; i < N; i++)
        {
                 int temp = 1;
                 for (int j = 0; j < N - 1; j++)
                         if (board[j + 1][i] == board[j][i])
                                 temp++;
                         else
                         {
                                 result = max(result, temp);
                                 temp = 1;
                         }
                 result = max(result, temp);
        }
        return result;
}
 
int main(void)
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cin >> N;
        for (int i = 0; i < N; i++) cin >> board[i];
        int result = 0;
        for(int i=0; i<N; i++)
                 for (int j = 0; j < N - 1; j++)
                 {
                         //양 옆 swap
                         swap(board[i][j], board[i][j + 1]);
                         result = max(result, numOfCandy());
                         swap(board[i][j], board[i][j + 1]);
                         //위 아래 swap
                         swap(board[j][i], board[j + 1][i]);
                         result = max(result, numOfCandy());
                         swap(board[j][i], board[j + 1][i]);
                 }
        cout << result << "\n";
        return 0;
}

funny algorithm*0* ~