글 읽기 - 반례를 찾습니다 ㅠㅠ

blue_sau 4년 전 0

게시판에 있는 반례들은 모두 돌려보았고, 전부 맞는 값인 것을 확인했습니다.

알고리즘 적으로도 틀릴만한 요소가 딱히 없는데요 ㅠㅠ

돌리자 마자 바로 틀렸습니다 라고 나옵니다.

#include<stdio.h>

int maximum[10][1024] = { 0, };
int array[10] = { 0, };
int mask[1024];
int bin[1024];

//범위는 1024이하로만 가능
int pow_2(int val) {
	if (val == 0) {
		return 1;
	}
	return pow_2(val - 1) * 2;
}


int count(int n) {
	int i = 0;
	int l = n;
	if (bin[n] >= 0) {
		return bin[n];
	}
	for (i = 0; l != 0; i++) {
		l &= (l - 1);
	}
	bin[n] = i;
	return i;
}


int getmask(int i) {
	int temp;
	if (mask[i] < 0) {
		temp = i;
		temp = (temp|(temp >> 1));
		mask[i] = temp;
		return temp;
	}
	else {
		return mask[i];
	}
}


void init() {
	int i,j;
	array[0] = 0;
	array[1] = 0;
	array[2] = 0;
	array[3] = 0;
	array[4] = 0;
	array[5] = 0;
	array[6] = 0;
	array[7] = 0;
	array[8] = 0;
	array[9] = 0;
	for (i = 0; i < 10; i++) {
		for (j = 0; j < 1024; j++) {
			maximum[i][j] = 0;
		}
	}
}

int overlap(int a,int b) {
	return !(a&b);
}

int main(void) {
	char temp;
	int m, n,i,j,k,l,max,pow,lmask,bmask;
	int testcase;
	scanf("%d", &testcase);
	for (i = 0; i < 1024; i++) {
		mask[i] = -1;
		bin[i] = -1;
	}
	for (i = 0; i < testcase; i++) {
		init();
		scanf("%d", &n);
		scanf("%d", &m);
		getchar();
		for (j = 0; j < n; j++) {
			pow = pow_2(j);
			for (k = 0; k < m; k++) {
				scanf("%c", &temp);
				if (temp == 'x') {
					array[k] += pow;
				}
			}
			getchar();
		}
		max = pow_2(n);
		//이니셜 값 지정
		for (j = 0; j < max; j++) {
			if ((array[0] & j) > 0) {
				maximum[0][j] = -1;
			}
			else {
				maximum[0][j] = count(j);
			}
		}
		//탐색 진행
		for (j = 1; j < m ; j++) {
			for (k = 0; k < max; k++) {
				if (k&array[j]) {
					continue;
				}
				int mtemp = 0;
				for (l = 0; l < max; l++) {
					if (maximum[j-1][l] < 0) {
						continue;
					}
					lmask = getmask(l);
					bmask = getmask(k);
					lmask &= k;
					bmask &= l;
					if (lmask == 0 && bmask == 0) {
						if (mtemp < maximum[j - 1][l]) {
							mtemp = maximum[j - 1][l];
						}
					}
				}
				maximum[j][k] = mtemp + count(k);
			}
		}
		int maxval = 0;
		for (j = 0; j <= max; j++) {
			if (maxval < maximum[m - 1][j]) {
				maxval = maximum[m - 1][j];
			}
		}
		printf("%d\n",maxval);
	}
	return 0;
}

holenet 4년 전 1

10
xxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxx

정답은 0이지만 올려주신 코드로는 1023이 출력됩니다.

n이 10미만일 때는 잘 작동하는데 n이 10일때 많은 경우에서 오답이 발생합니다.

인덱스 설정을 잘못하신게 아닌지 확인해보시면 좋을 것 같습니다.

blue_sau 4년 전 0

헐 ㅠㅠ

너무 감사합니다 ㅠ

blue_sau 4년 전 0

마지막 max값 도출에서 0~max-1까지인데, 0~max로 잡아서 그런 거였네요 ㅠㅠ

정말 감사합니다.

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

문제

문제

출처

ICPC

반례를 찾습니다 ㅠㅠ

blue_sau 4년 전 0

holenet 4년 전 1

blue_sau 4년 전 0

blue_sau 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말