백준 3085 C++

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

3085번: 사탕 게임

 

문제 정리

문자가 들어있는 보드 값이 주어지면 위치를 서로 바꿔 같은 행이나 열을 만들면 사탕을 먹을 수 있다.

먹을 수 있는 최대 사탕의 개수를 구하는 문제

 

생각

음... 근데 이동만 하면 3의 배수로 사탕이 없어지는 거 아닌가?

아닌가 문제 이해를 잘못했나...

-> 먹으면 그 다음은 이동을 못하나봐

 

문제 이해!!!! 그냥 딱 한 번만 바꿨을 때 최대의 사탕을 구하면 된다!

 

상하좌우 4방향을 전부 검사할 것인지, 두 방향만 고정해서 반복되는 경우를 줄일 것인지 선택을 해야된다

그냥 중복되는 경우를 줄이기 위해 오른쪽과 아래 방향으로 이동만 검사를 해야겠다.

 

 

1. 오른쪽 방향 이동 구현

현재 인덱스와 오른쪽 인덱스를 교환후 최대 사탕 수를 저장한다

전과 비교 후 최대를 저장한다

원상복귀 후 다음 인덱스로 넘어가 계속 검사를 해준다

 

2. 아래 방향 이동 구현

현재 인덱스와 아래 방향 인덱스를 교환후 최대 사탕 수를 저장한다

전과 비교 후 최대를 저장한다

원상복귀 후 다음 인덱스로 넘어가 계속 검사를 해준다

 

max 오른쪽, 아래 둘 다 저장하고 마지막에 두 개 비교해서 더 큰 거 답으로 하면 될 듯!

 

코드

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

int maxcount=0;

// 가로 바꾸는 거
void rowCount(char arr[50][50], int size){
    for(int i=0 ; i<size ; i++){
        int count = 1;
        for(int j=0 ; j<size-1 ; j++){
            if(arr[i][j] == arr[i][j+1]){
                count++;
            }
            else{
                if(count > maxcount){
                    maxcount = count;
                }
                count = 1;
            }
        }
    }
}

// 세로 바꾸는 거
void columnCount(char arr[50][50], int size){
    for(int i=0 ; i<size ; i++){
        int count = 1;
        for(int j=0 ; j<size-1 ; j++){
            if(arr[j][i] == arr[j+1][i]){
                count++;
            }
            else{
                if(count > maxcount){
                    maxcount = count;
                }
                count = 1;
            }
        }
    }
}

int main() {
    int n;
    char board[50][50];
    cin >> n;

    // 입력
    for(int i=0 ; i<n ; i++){
        for(int j=0 ; j<n ; j++){
            cin >> board[i][j];
        }
    }

    for(int i=0 ; i<n ; i++){
        for(int j=0 ; j<n-1 ; j++){
            // 가로 swap 후 maxcount 찾기 이후 원위치로 돌려놓기
            swap(board[i][j], board [i][j+1]);
            columnCount(board, n);
            rowCount(board, n);
            swap(board[i][j+1], board[i][j]);

            // 세로 swap 후 maxcount 찾기 이후 원위치로 돌려놓기
            swap(board[j][i], board[j+1][i]);
            columnCount(board, n);
            rowCount(board, n);
            swap(board[j+1][i], board[j][i]);
        }
    }
    cout << maxcount;
}

 

원위치로 돌려놓는 게 잠깐 헷갈렸는데 간단하게 돌려놓을 수 있다!

각 swap 이후에 다시 원래의 값으로 복구시켜주면 되는데 -> 각각의 swap 이후에 다시 swap 해주면 된다! 인자 두 개 위치 바꾸면 됨