글 읽기 - 1058 - 이런 방식으로 풀면 안되나요? 반례 부탁 드립니다.

CHULMING 5년 전 0

플로이드로 다시 짜서 정답은 받았습니다

근데 처음에 생각했던 아이디어가 오답인 이유가 궁금하네요..

아이디어는 이렇습니다.

A와 B가 친구('Y')일 때, B의 친구들은 모두 A와 2-친구이다.

arr[A][B] == 'Y'라면, B행에 있는 모든 'Y'인 열에 대해 A와 2-친구 표시를 했습니다. (배열에 A의 2-친구들은 모두 2로 표기)

이런 방식으로 풀면 어떤 예에서 틀리나요?

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>

using namespace std;

char arr[51][51];
int ans[51];
int main() {

	int n,mx = 0;
	scanf("%d", &n);
	
	for (int i = 0; i < n; i++)
		scanf("%s", arr[i]);

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (i == j || arr[i][j] != 'Y') continue;
			
			for (int z = 0; z < n; z++) {
				if (z == i || arr[j][z] != 'Y' ) continue;
				arr[i][z] = '2';
			}

		}

	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++)
			if (arr[i][j] != 'N') ans[i]++;
		mx = max(mx, ans[i]);
	}
	printf("%d\n", mx);
	return 0;
}

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

문제

문제

출처

ICPC

1058 - 이런 방식으로 풀면 안되나요? 반례 부탁 드립니다.

CHULMING 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말