글 읽기 - 예외적인 케이스나 잘못된 부분 지적 부탁드립니다.

tera1130 8년 전 0

기본적인 결과 값은

모든 경우의 수 - (불가능한 모든 조합 수 + 불가능조합 중 중복되는 조합 수) 로 했고

불가능 조합으로 1 2, 2 3, 1 3 같은 수를 입력 받으면 불가능한 조합 중 같은 조합이 3개가 나오는 경우가 있길래

그런 경우에는 기존에 사용한 공식과 1만큼 오차가 생겨서 결과값에 1을 빼도록 했습니다.

#include <iostream>
using namespace std;

int main()
{
	int ice_kind, comb_num, result;				// 아이스크림 종류, 조합종류, 결과
	cin >> ice_kind >> comb_num;
	int* ice_num = new int[ice_kind+1];			// 불가능 조합에 포함된 각 아이스크림별 개수
	int* comb_list = new int[comb_num*2];		// 조합 수 * 조합별 아이스크림(2개)
	int* cont1 = new int[ice_kind+1];			// 연속된 숫자를 받았을때 확인용
	int* cont2 = new int[ice_kind+1];			// 한칸 건넌 숫자를 받았을때 확인용
	int overlap = 0;							// 불가능한 조합 중 중복된 수
	for (int i = 0; i < ice_kind+1; i++)		// 동적배열 초기화
	{
		ice_num[i] = 0;
		cont1[i] = 0;
		cont2[i] = 0;
	}
	for (int i = 0; i < comb_num * 2; i+=2)		// 조합 입력
	{
		cin >> comb_list[i] >> comb_list[i+1];
		ice_num[comb_list[i]]++;
		ice_num[comb_list[i+1]]++;
		if (comb_list[i] + 1 == comb_list[i + 1])		// 연속된 숫자를 받았을 경우 cont1 배열에 저장
		{
			cont1[comb_list[i]]++;
		}
		else if (comb_list[i] + 2 == comb_list[i + 1])	// 한칸 건넌 숫자를 받았을 경우 cont2 배열에 저장
		{
			cont2[comb_list[i]]++;
		}
	}
	for (int i = 0; i < ice_kind + 1; i++)				// 조합 중 중복된 수만큼 overlap 변수에 저장
	{
		ice_num[i] = ice_num[i] * (ice_num[i] - 1) / 2;
		overlap += ice_num[i];
	}
	if (ice_kind < 3)			// 아이스크림 종류가 3개 미만이면 결과 0
	{
		result = 0;
	}
	else		// 아이스크림 종류가 3개 초과이면
	{
		result = ice_kind*(ice_kind - 1)*(ice_kind - 2) / 6 - comb_num*(ice_kind - 2) + overlap; // 전체 경우의 수 - 조합수*(종류-2) + 중복된 조합의 수
	}
	
	for (int i = 1; i < ice_kind; i++)
	{
		if (cont1[i] == 1 && cont1[i + 1] == 1 && cont2[i] == 1)			// 중복된 조합에서 같은 수가 3개가 나오면 result 1 감소
		{
			result--;
		}
	}

	cout << result;
}

f52985 8년 전 0

4 3

1 2

2 3

3 1

정답 : 0

출력 : 1

아마도 위 예시와 같이 삼각형 사이클이 생기는 경우는 처리가 잘 안되는 것 같네요

tera1130 8년 전 0

조합 입력 시 앞 숫자가 크면 제대로 처리가 안된것 같아서

입력 받을 때

if (temp1 >= temp2)
{
comb_list[i] = temp2;
comb_list[i + 1] = temp1;
}
else
{
comb_list[i] = temp1;
comb_list[i + 1] = temp2;
}

추가해서 수정하니 0이 나오기는 합니다. 계속 예외적인 결과가 나오니

알고리즘 자체가 잘못된것 같기도 한데... 현재 알고리즘으로도 해결 가능한건가요?

#include <iostream>
using namespace std;

int main()
{
	int ice_kind, comb_num, result;				// 아이스크림 종류, 조합종류, 결과
	cin >> ice_kind >> comb_num;
	int* ice_num = new int[ice_kind+1];			// 불가능 조합에 포함된 각 아이스크림별 개수
	int* comb_list = new int[comb_num*2];		// 조합 수 * 조합별 아이스크림(2개)
	int* cont1 = new int[ice_kind+1];			// 연속된 숫자를 받았을때 확인용
	int* cont2 = new int[ice_kind+1];			// 한칸 건넌 숫자를 받았을때 확인용
	int overlap = 0;							// 불가능한 조합 중 중복된 수
	int temp1, temp2;
	for (int i = 0; i < ice_kind+1; i++)		// 동적배열 초기화
	{
		ice_num[i] = 0;
		cont1[i] = 0;
		cont2[i] = 0;
	}
	for (int i = 0; i < comb_num * 2; i += 2)		// 조합 입력
	{
		if (temp1 >= temp2)
		{
			comb_list[i] = temp2;
			comb_list[i + 1] = temp1;
		}
		else
		{
			comb_list[i] = temp1;
			comb_list[i + 1] = temp2;
		}
		ice_num[comb_list[i]]++;
		ice_num[comb_list[i+1]]++;
		if (comb_list[i] + 1 == comb_list[i + 1])		// 연속된 숫자를 받았을 경우 cont1 배열에 저장
		{
			cont1[comb_list[i]]++;
		}
		else if (comb_list[i] + 2 == comb_list[i + 1])	// 한칸 건넌 숫자를 받았을 경우 cont2 배열에 저장
		{
			cont2[comb_list[i]]++;
		}
	}
	for (int i = 0; i < ice_kind + 1; i++)				// 조합 중 중복된 수만큼 overlap 변수에 저장
	{
		ice_num[i] = ice_num[i] * (ice_num[i] - 1) / 2;
		overlap += ice_num[i];
	}
	if (ice_kind < 3)			// 아이스크림 종류가 3개 미만이면 결과 0
	{
		result = 0;
	}
	else		// 아이스크림 종류가 3개 초과이면
	{
		result = ice_kind*(ice_kind - 1)*(ice_kind - 2) / 6 - comb_num*(ice_kind - 2) + overlap; // 전체 경우의 수 - 조합수*(종류-2) + 중복된 조합의 수
	}
	
	for (int i = 1; i < ice_kind; i++)
	{
		if (cont1[i] == 1 && cont1[i + 1] == 1 && cont2[i] == 1)			// 중복된 조합에서 같은 수가 3개가 나오면 result 1 감소
		{
			result--;
		}
	}

	cout << result;
}

f52985 8년 전 0

글쎄요.. 제가 아직 이 알고리즘을 확실히 이해하지는 못해서 가능할지는 확답을 드릴 수 없겠네요.

아마 이 알고리즘으로도 해결이 불가능하진 않겠지만, 너무 정교한 계산을 요구해서 어디서 실수가 있는지를 찾기가 힘드네요..

정 안된다면 N이 200밖에 안되므로 N^3의 brute force search도 고려해보시면 좋을 것 같습니다.
다만 성공한다면 N^3짜리 알고리즘 보다는 훨씬 효율적인 알고리즘이 될거라고 생각합니다.

일단 두번째 소스코드에서는 temp1,temp2를 입력받는 부분이 누락되었는데, 여기서 입력을 받도록 고쳐도 예외 테스트케이스가 있네요.

5 3
1 2
2 5
5 1
정답 : 3
출력 : 4

tera1130 8년 전 0

1 2, 2 3, 3 1 처럼 수가 연속된 경우만 생각했네요.

계속 한가지 방법만 생각하니 잘 안되는 것 같네요.

brute force search도 참고해보고 다른 알고리즘도 생각을 해봐야 겠습니다.

자세한 답변 감사합니다....

tera1130 8년 전 0

알고리즘 새로 짰는데도 예외가 발생하는지 틀렸다고 나오네요...

이번에는 이차원 벡터로 해봤는데 왜 또 안되는지.... ㅜㅜ

이번에는 어떤 예외때문일까요?

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	int ice_kind, temp_ice_kind, comb_num, exp_num = 0;
	int cin_comb[2];
	vector < vector<int> > comb_list;
	cin >> ice_kind >> comb_num;
	temp_ice_kind = ice_kind;
	for (int i = 0; i < ice_kind+1; i++){
		vector<int> element;
		comb_list.push_back(element);
	}
	for (int i = 0; i < comb_num; i++){
		cin >> cin_comb[0] >> cin_comb[1];
		comb_list[min(cin_comb[0], cin_comb[1])].push_back(max(cin_comb[0], cin_comb[1]));
	}
	for (int i = 1; i < ice_kind + 1; i++){
		if (ice_kind < 3)
			break;
		int size = comb_list[i].size();
		for (int j = 0; j < size; j++){
			exp_num += (temp_ice_kind - 2 - j);
		}
		if (comb_list[i].size() != 0){
			temp_ice_kind--;
		}
	}
	cout << ice_kind*(ice_kind - 1)*(ice_kind - 2) / 6 - exp_num;
}

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

문제

문제

출처

ICPC

예외적인 케이스나 잘못된 부분 지적 부탁드립니다.

tera1130 8년 전 0

f52985 8년 전 0

tera1130 8년 전 0

f52985 8년 전 0

tera1130 8년 전 0

tera1130 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말