[2017 홍익대학교 프로그래밍 경진대회] 14926번 Not Equal

문제

주어진 N개의 수가 모두 서로 다르다는 것은 기호 "!="를 통해 하나의 식으로 표현할 수 있다. 예를 들어 A, B, C가 모두 서로 다르다는 것은 논리식으로 (A != B) && (B != C) && (C != A) 로 쓸 수 있고, 이를 다음과 같이 한 줄로 표현하는 것을 A, B, C에 대한 "한 줄 표기법"이라고 부르기로 하자.

A != B != C != A

하지만 5개의 수 A, B, C, D, E가 모두 서로 다르다는 것을 다음처럼 표현하는 것은 올바른 한 줄 표기법이 아니다.

A != B != C != D != E

왜냐하면 5개의 수가 서로 다름을 나타내기 위해서는 10개의 쌍에 대해 서로 다름을 표현해야 하고, 이는 적어도 10개의 "!="를 필요로 하기 때문이다. 일반적으로 주어진 N개의 수가 모두 다름을 한 줄 표기법으로 표현하기 위해서는 적어도 C(N, 2)개의 "!="이 필요함이 알려져 있다(C(N, 2) : N개의 서로 다른 대상 중 2개를 뽑는 가짓수).

홀수 자연수 N이 주어졌을 때, N개의 수 a1, a2, …, aN에 대해 가능한 한 줄 표기법 중 가장 짧으면서 사전순으로 가장 앞에 오는 한 줄 표기법을 출력하는 프로그램을 작성하라. 단 이때 "!="은 공백으로 대신하기로 한다. 예를 들어 N = 3이 주어졌을 때 "a1 a2 a3 a1"는 정답으로 인정되지만, "a3 a1 a2 a3"는 사전순으로 앞의 표기법보다 뒤에 오기 때문에 올바른 한 줄 표기법이라도 정답으로 인정되지 않는다.

Hint : 한 줄 표기법에 최소로 필요한 "!="의 개수인 C(N, 2)는 Vertex가 N개인 완전 그래프의 Edge의 개수와 동일함을 고려해 보라.

입력

첫째 줄에 자연수 N이 주어진다. N은 1보다 크고 500보다 작은 홀수이다.

출력

첫째 줄에 가능한 한 줄 표기법 중 가장 짧으면서 사전순으로 가장 앞에 오는 것을 출력한다.

 

 

vertex 수가 많아 완탐으로는 불가능이고 브루트포스 식으로 해야한 단 것은 깨달았는데, 딱히 방법이

바로 떠오르진 않은 문제.

우선 n개의 정점의 경우 모든 정점을 잇는 간선이 n(n-1)/2개 이므로 이 간선 횟수만큼 반복하면서

이미 체크된 간선인지 아닌지 확인하는 작업이 필요하다.

 

0에서 시작하면서 1로 넘어와서 반복하면서 간선을 통한 새로운 이동이라면 출력

이미 체크한 간선혹은 자기 자신이라면 넘어간다.

마지막엔 최종 간선은 자기 자신으로 돌아오게 되므로 a1을 출력하고 마무리.

 

직관적으로는 이해가 힘든 느낌..

#include<iostream>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
#include<stack>
#include<set>
#include<map>
using namespace std;

bool edge[501][501];

int main() {
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL);

	int n;
	cin >> n;
	int curvex = 0;

	edge[1][n] = edge[n][1] = true;

	for (int i = 0; i < (n * (n - 1) )/ 2; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (curvex == j || edge[curvex][j])
				continue;
			edge[curvex][j] = edge[j][curvex] = true;
			curvex = j;
			break;
		}
		cout << "a" << curvex << " ";
	}
	cout << "a1";

}