글 읽기 - [C - 체스판 다시 칠하기] 게시판의 모든 반례에 대해서 잘 동작합니다.

konichan7 4년 전 0

변수도 많고 for loop도 많아서 많이 번잡하네요..
게시판에 있는 질문들을 한번씩 들어가보고 틀린 부분을 하나씩 고쳤습니다.

1)
8 8
WWWWWWWW
WWWWWWWW
WWWWWWWW
WWWWWWWW
WWWWWWWW
WWWWWWWW
WWWWWWWW
WWWWWWWW

2)
8 9
WBWBWBWBB
BWBWBWBWW
WBWBWBWBB
BWBWBWBWW
WBWBWBWBB
BWBWBWBWW
WBWBWBWBB
BWBWBWBWW

이 두 경우에 대해서 틀린 답이 나와서 고쳤는데, 혹시 또 다른 반례가 있을까요?
틀린 부분이 있다면 지적 부탁드리겠습니다

감사합니다.

#include<stdio.h>
int main(void){
	int n,m,maxIndex_R,maxIndex_C;
	int maxrow=-1,maxCol=-1,sum=0,caseB=0,caseW=0;
	char board[51][51];
	int rowScore[51]={0};
	int colScore[51]={0};
	scanf("%d %d",&n,&m);
	for(int i=0;i<n;i++){
		scanf("%s",board[i]);
		for(int j=0;j<m-1;j++){
			if(board[i][j]!=board[i][j+1]) rowScore[i]+=1;
            //각각의 행에서 같은 문자가 반복되지 않을 수록 rowScore가 높아집니다.
		}
	}
	for(int i=0;i<n-7;i++){
		for(int j=i;j<i+8;j++){
			sum+=rowScore[j];
		}
		if(sum>maxrow){
			maxrow=sum;
			maxIndex_R=i;
		}sum=0;
        //rowScore가 높은 8개의 행을 찾습니다.
	}
	for(int j=0;j<m;j++){
		for(int i=maxIndex_R;i<maxIndex_R+7;i++){
			if(board[i][j]!=board[i+1][j]) colScore[j]+=1;
            //rowScore처럼, 각각의 열에서 같은 문자가 반복되지 않을 수록 colScore가 높아집니다.
		}
	}
	for(int j=0;j<m-7;j++){
		for(int k=j;k<j+8;k++){
			sum+=colScore[k];
		}
		if(sum>maxCol){
			maxCol=sum;
			maxIndex_C=j;
		}sum=0;
	}
	for(int i=maxIndex_R;i<maxIndex_R+8;i++){
		for(int j=maxIndex_C;j<maxIndex_C+8;j++){
			if((i+j)%2==0){
				if(board[i][j]!='W') caseW+=1;
				else caseB+=1;
			}
			else{
				if(board[i][j]!='B') caseW+=1;
				else caseB+=1;
			}
		}
	}
	printf("%d",(caseW)>(caseB)?(caseB):(caseW));	
	return 0;
}

konichan7 4년 전 0

모든 경우를 생각하려니 더 문제가 복잡해지네요.
브루트 포스 알고리즘 유형에 해당하는 문제인 만큼 단순하게 생각하면 코드 라인 수도 훨씬 짧아지고 반례를 생각할 필요도 없는 문제였습니다.

이와 별개로 위의 코드에서 간과하고 있었던 반례는
9 8
BWBWBWBW
WBWBWBWB
BWBWBWBW
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB

였는데 이 부분을 염두에 두고 고쳐도 또 다른 반례가 있는지 틀렸다네요..

hyeon0528 3년 전 0

konichan7님 알려주신 경우에 답이 몇이 나와야하나요 ?

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

문제

문제

출처

ICPC

[C - 체스판 다시 칠하기] 게시판의 모든 반례에 대해서 잘 동작합니다.

konichan7 4년 전 0

konichan7 4년 전 0

hyeon0528 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말