글 읽기 - 반례 좀 찾아주세요.(코드 주석 모두 달아놨습니다.)

dydrhks7 2년 전 0

테스트 케이스 모두 맞고

1 2

2 3

4 5

6 1

로해서 <1,6>,<2,3>,<4,5>로 이어지는 부분이나 (답:6)

1 2

2 3

3 1

4 5

5 6

6 4

로 해서 <1,2>,<4,5>로 이어지는 부분도 해결되었습니다.(답 : 5)

계속 틀렸습니다가 나와서 그런데

혹시 어느 부분이 잘못되었는지 부탁드립니다. 아니면 제가 문제를 잘못 이해한 부분이 있는지 부탁드립니다.

#include<iostream>
#include<algorithm>
#include<cstring>
#include<numeric>
#define endl "\n"


using namespace std;

int main() {

	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	int n;
	int m;
	cin >> n;
	cin >> m;

	int relations[55] = { 0, }; //관계 배열

	int a;
	int b;

	for (int i = 1; i <= m; i++) {
		cin >> a >> b;
		relations[a] = b; //관계 그리기.
	}

	int count = 0;
	int total_count = 0;

	int relation_check[55] = { 0, }; //관계를 체크하는 배열

	for (int j = 1; j <=n; j++) { //1부터 n까지 돌려보자.
		memset(relation_check, 0, sizeof(relation_check)); //관계체크 초기화.
		count = 0;
		for (int i = j; i <=n; i++) {//i는 j부터시작해서 n까지 돌려보기.
			if (relation_check[i] != 0) { //만일 관계가 이미 되어있다면 다음걸로 넘어가자.
				continue;
			}
			if (relations[i] == 0) //만일 관계가 아무하고도 없다면 넘어가자. (다른쪽에서 연결되어있다면 그 쪽에서 연결이 될 것이다.)
				continue;
			if (relation_check[relations[i]] != 0) //만일 관계 체크가 될 값이 이미 차지되어있다면 넘어가자. ex. <1,2>,<3,1>이라면 뒤에 있는 3은 1과 관계를 맺어야하므로 다음으로 넘어가자.
				continue;
			relation_check[relations[i]] = 1; //관계 맺는 곳을 체크시키자.
			relation_check[i] = 1; //관계를 자기한테도 체크하자.
			count += 2; //양쪽으로 이어지므로 2씩을 더하자.
		}

		total_count = max(total_count, count); //최대 맥스값 찾기.
	}

	if (total_count<n) //만일 n보다 작다면 비어있는 부분이 있다는 거고 가운데에 1명을 추가로 부를 수 있을 것이다.
		cout << total_count + 1 << endl;
	else //만일 전체 숫자만큼 부른다면 추가로 부를 수가 없다.
		cout <<  total_count << endl;

	
	return 0;
}

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

문제

문제

출처

ICPC

반례 좀 찾아주세요.(코드 주석 모두 달아놨습니다.)

dydrhks7 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말