글 읽기 - 1217번 힌트나 반례좀요 ㅠㅠ

gkfkagkfka12 6년 전 0

단순히 조합문제로 여겨져서 그렇게 풀었는데 50%에서 계속 틀리네여...

힌트나 반례 없을까요?

#include <cstdio>

int house[20001];

int main(void)
{
	int n, m; scanf("%d%d", &n, &m);
	int symp1, symp2;
	bool alive = false;

	while (n && m){
		for (int i = 0; i < n; i++) {
			scanf("%d%d", &symp1, &symp2);
			if (symp1 < 0) symp1 *= -1;
			if (symp2 < 0) symp2 *= -1;
			house[symp1]++;
			house[symp2]++;
		}
		int num = 1;
		num = 2 * (m - 1) * 2;
		for (int i = 1; i <= m; i++){
			if (house[i] != num){
				alive = true;
				break;
			}
		}

		alive ? printf("1\n") : printf("0\n");
		alive = false;
		for (int i = 1; i <= m; i++) house[i] = 0;
		scanf("%d%d", &n, &m);
	}
	return 0;
}

jh05013 6년 전 0

무슨 풀이인지 모르겠습니다. 답이 정말로 N과 M에만 의존할까요?

gkfkagkfka12 6년 전 0

@jh05013 코드를 수정했는데도 틀리네요...ㅠㅠ

jh05013 6년 전 0

여전히 무슨 풀이인지 모르겠습니다.

gkfkagkfka12 6년 전 0

죽을 수 밖에 없는 조건이 질병의 종류에 대한 모든 경우의 수라서 규칙의 종류가 그 경우의 수를 만족하지 못하는 경우 사는 겁니다.

예제처럼 질병의 종류가 3개라면 죽을 수 밖에 없는 경우는

1 2 , 1 3, -1 2, -1 3, 1 -2, 1 -3, -1 -2, -1 -3, 2 3, 2 -3, -2 3, -2 -3으로 총 12가지 경우인데

자기자신과 그 음수가 총 8번씩 등장합니다. 이 등장횟수가 2*(m-1)*2라서 이 등장횟수를 만족시키는 지 확인하는 겁니다.

코드 수정했으니 다시봐주세여

jh05013 6년 전 0

꼭 모든 규칙이 나타나야 되는 건 아닙니다. 다음 입력의 답은 0입니다.

gkfkagkfka12 6년 전 0

그럼 규칙을 나열할 때 나타나는 최대의 숫자에 의존한다는뜻인가요?

jh05013 6년 전 1

숫자가 나타나는 횟수는 답과 큰 관계가 없습니다.

실제 풀이는 더 복잡합니다. 이 문제는 전형적인 2-SAT 문제인데, 푼 문제 목록을 보니 아직 풀만한 단계는 아닌 것 같습니다.

gkfkagkfka12 6년 전 0

넵....ㅠㅠㅠㅠ

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