글 읽기 - 3085 사탕 게임 애매한 설명

onjo0127 8년 전 0

문제에서

"이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다."

이 부분이 명확하지 않습니다.

사탕을 교환한 다음 바뀐 두 칸의 행,열에서만 탐색해야 하는지, 아니면 모든 행,열을 탐색하는 것인지 나와 있지 않습니다.

그리고 아예 사탕을 바꿀 수 없을 때

예)

CCC

이럴 때는 서로 다른 색이 없어서 바꿀 수가 없는데 최대값은 어떻게 처리하나요? 이 상태에서 바꾸지 않고 먹을 수 있나요?

아래는 제 소스코드입니다.

완전탐색했습니다.

이 문제 맞으신 분들은 어떻게 풀으셨는지 궁금합니다.

도와주세요!

#include <stdio.h>

char board[59][59];
int max = 0;

void Swap(char& a,char& b)
{
    char imsi = a;
    a = b;
    b = imsi;
}

int main()
{
    int n,i,j,x,cnt;
    scanf("%d",&n);

    for(i=0;i<n;i++) {
        for(j=0;j<n;j++) {
            scanf(" %c",&board[i][j]);
        }
    }

    for(i=0;i<n;i++) {
        for(j=0;j<n-1;j++) {
            if(board[i][j]!=board[i][j+1]) {
                Swap(board[i][j],board[i][j+1]);

                cnt=0;
                for(x=j;x>=0 && board[i][x] == board[i][j];x--)++cnt;
                if(max<cnt)max=cnt;

                cnt=0;
                for(x=j+1;x<n && board[i][x] == board[i][j+1];x++)++cnt;
                if(max<cnt)max=cnt;

                cnt=0;
                for(x=i;x>=0 && board[x][j] == board[i][j];x--)++cnt;
                for(x=i;x<n && board[x][j] == board[i][j];x++)++cnt;
                if(max<cnt-1)max=cnt-1;

                cnt=0;
                for(x=i;x>=0 && board[x][j+1] == board[i][j+1];x--)++cnt;
                for(x=i;x<n && board[x][j+1] == board[i][j+1];x++)++cnt;
                if(max<cnt-1)max=cnt-1;

                Swap(board[i][j],board[i][j+1]);
            }
        }
    }

    for(i=0;i<n-1;i++) {
        for(j=0;j<n;j++) {
            if(board[i+1][j]!=board[i][j]) {
                Swap(board[i][j],board[i+1][j]);

                cnt=0;
                for(x=j;x>=0 && board[i][x] == board[i][j];x--)++cnt;
                for(x=j;x<n && board[i][x] == board[i][j];x++)++cnt;
                if(max<cnt-1)max=cnt-1;

                cnt=0;
                for(x=j+1;x<n && board[i][x] == board[i][j+1];x++)++cnt;
                for(x=j+1;x>=0 && board[i][x] == board[i][j+1];x--)++cnt;
                if(max<cnt-1)max=cnt-1;

                cnt=0;
                for(x=i;x>=0 && board[x][j] == board[i][j];x--)++cnt;
                if(max<cnt)max=cnt;

                cnt=0;
                for(x=i;x<n && board[x][j] == board[i][j];x++)++cnt;
                if(max<cnt)max=cnt;

                Swap(board[i][j],board[i+1][j]);
            }
        }
    }

    printf("%d",max);
    return 0;
}

iljimae 8년 전 4

안녕하세요 onjo님! (저 블로그 친구에요 ㅋㅋ)

각 사탕마다 인접해있는 사탕끼리 위치를 바꾸고 바뀐 곳에서만 탐색을 했더니 테스트 케이스를 다 통과하더라구요. 예를 들어서 (i,j)에 있는 사탕을 옆에 인접해있는 사탕과

위치를 바꾸었을때는 i행, j열,그리고 (j+1)번째 열만 탐색하고 최댓값을 갱신했구요, 아래에 인접해있는 사탕과 위치를 바꾸었을때는 i행, (i+1)행 그리고 j열만 탐색해서 최댓값을 갱신했어요. 제 C++ 소스 첨부해볼게요:

// brute force search. 
#include <iostream> 
#include <cstdlib>
#include <algorithm> 
#include <vector> 
#include <string>
using namespace std; 

int N; 
char grid[51][51]; 

bool inRange(int y, int x){
	return (y >= 0 && y < N && x >= 0 && x < N);
}

int longestConsecutiveChar(string s){
	int cnt = 0, temp = 1; 
	for (int i = 0; i < s.size()-1; i++){
		if (s[i] == s[i+1]) ++temp;  
		else{
			cnt = max(cnt,temp);  
			temp = 1;  
		}
	}	
	cnt = max(cnt,temp); 
	return cnt;  
}

int main(){
	// get input. 
	cin >> N; 
	for (int i = 0; i < N; i++){
		for (int j = 0; j < N; j++){
			cin >> grid[i][j]; 
		}
	}
	int maxCnt = 0;  
	// swap 
	// this is an O(N^3) algorithm. 
	for (int i = 0; i < N; i++){
		for (int j = 0; j < N; j++){
			// swap characters horizontally
			// we only need to check row i, cols j,j+1 for updates
			if (inRange(i,j+1)){
				swap(grid[i][j],grid[i][j+1]);  
				string a,b,c; 
				for (int k = 0; k < N; k++){ // row i
					a += grid[i][k];  
				}
				for (int k = 0; k < N; k++){ // col j
					b += grid[k][j];  
				}
				for (int k = 0; k < N; k++){ // col j+1
					c += grid[k][j+1]; 
				}
				int v1 = longestConsecutiveChar(a), v2 = longestConsecutiveChar(b), v3 = longestConsecutiveChar(c); 
				maxCnt = max(maxCnt,max(v1,max(v2,v3)));   
				swap(grid[i][j],grid[i][j+1]);  
			}
			// swap characters vertically 
			// we only need to check rows i,i+1 and col j for updates  
			if (inRange(i+1,j)){
				swap(grid[i][j],grid[i+1][j]); 
				string a,b,c; 
				for (int k = 0; k < N; k++){ // row i 
					a += grid[i][k];  
				}
				for (int k = 0; k < N; k++){ // row i+1
					b += grid[i+1][k]; 
				}
				for (int k = 0; k < N; k++){ // col j
					c += grid[k][j];  
				}
				int v1 = longestConsecutiveChar(a), v2 = longestConsecutiveChar(b), v3 = longestConsecutiveChar(c);  
				maxCnt = max(maxCnt,max(v1,max(v2,v3))); 
				swap(grid[i][j],grid[i+1][j]);  
			}
		}
	}
	cout << maxCnt << endl; 
	return 0; 
}

onjo0127 8년 전 1

안녕하세요 stardust님!

저도 블로그 잘 보고 있어요.

힌트 주셔서 감사합니다! 다시 풀어봐야겠네요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

3085 사탕 게임 애매한 설명

onjo0127 8년 전 0

iljimae 8년 전 4

onjo0127 8년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말