백준 BOJ 3085 - 사탕 게임

브루트포스문제

수가 워낙 작아서

ㄹㅇ 무식하게 풀 수 있었다.

 

www.acmicpc.net/problem/3085

3085번: 사탕 게임

원래는 O(N^2)에 dx dy 넣어서 판별하는거겠지만

dxdy 세그폴트안나게 잘 관리하는거도

걍 귀찮아서

x1 y1 x2 y2 뽑아놓고

둘이 바로 옆에있으면 계산하게끔 짜서

시간복잡도가 O(N^4)다....

 

#include <stdio.h>

char arr[51][51] = {0};
int n;
int ans=0;

int abs(int a){return a>0?a:a*-1;}
int max(int a, int b){return a>b?a:b;}
void swap(int x1,int y1, int x2, int y2){
	int tmp = arr[x1][y1];
	arr[x1][y1] = arr[x2][y2];
	arr[x2][y2] = tmp;
}

int count(){
	int cnt, ret=0;
    char pre;
    
    for(int i=0; i<n; i++){
        cnt = 1; pre = arr[0][i];
        for(int j=1; j<=n; j++){
            if(pre == arr[j][i]) cnt++;
            else{
            	pre = arr[j][i];
                ret = max(ret,cnt);
                cnt = 1;
            }
        }
    }
    for(int i=0; i<n; i++){
        cnt = 1; pre = arr[i][0];
        for(int j=1; j<=n; j++){
            if(pre == arr[i][j]) cnt++;
            else{
            	pre = arr[i][j];
                ret = max(ret,cnt);
                cnt = 1;
            }
        }
    }
    return ret;
}

int main(){
	scanf("%d", &n);
	for(int x1=0; x1<n; x1++){
		scanf("%s", &arr[x1]);
	}
	
	for(int x1=0; x1<n; x1++) for(int y1=0; y1<n; y1++){
		for(int x2=0; x2<n; x2++) for(int y2=0; y2<n; y2++){
			if(abs(x1-x2) == 1 && abs(y1-y2) == 0){
				swap(x1,y1,x2,y2);
				ans = max(ans, count());
				swap(x1,y1,x2,y2);
			}
			if(abs(x1-x2) == 0 && abs(y1-y2) == 1){
				swap(x1,y1,x2,y2);
				ans = max(ans, count());
				swap(x1,y1,x2,y2);
			}
		}
	}
	printf("%d", ans);
	return 0;
}

앞의 함수들부터 보자면

int abs(int a)는 절댓값

int max(int a, int b)는 둘중 큰 수

void swap(int x1,int y1,int x2,int y2) 는 arr[x1][y1]과 arr[x2][y2]를 스왑하는 함수이다.

 

int count()는 먹을수있는 사탕의 최대갯수를 반환하는 함수인데,

        for(int j=1; j<=n; j++){
            if(pre == arr[j][i]) cnt++;
            else{
            	pre = arr[j][i];
                ret = max(ret,cnt);
                cnt = 1;
            }
        }

이 부분에서 1부터 시작한것은 기초값이 윗줄에 미리 정해져있기 때문이며,

만약 pre가 arr의 값과 다르다면 pre를 갱신해주면서 최대값또한 갱신한다.

이렇게 해주는 이유는 앞에 캔디 두쌍 후 뒤에 캔디 3쌍같은경우는

실제로 최대값이 3이기 때문에

pre를 갱신해줘야 3까지 제대로 가져올 수 있다.

그리고 j<=n이기 때문에 배열의 제일 끝부분인 '\0'과도 비교를 하기 때문에

정상적으로 마지막 값을 ret에 넣을 수 있다.

 

if(abs(x1-x2) == 1 && abs(y1-y2) == 0){

main함수의 이 줄은 두 위치가 서로 근접해있는지를 판별한다.

 

이정도만 신경써주면

깔끔하게 AC.

구현이 좀 귀찮았다.