시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 109 74 62 74.699%

문제

주어진 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보다 작은 홀수이다.

출력

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

예제 입력 1

3

예제 출력 1

a1 a2 a3 a1

예제 입력 2

5

예제 출력 2

a1 a2 a3 a1 a4 a2 a5 a3 a4 a5 a1

출처

University > 홍익대학교 > 2017 홍익대학교 컴퓨터공학과 코딩대회 I번

  • 어색한 표현을 찾은 사람: doju
  • 잘못된 조건을 찾은 사람: jh05013
  • 문제를 만든 사람: lhw941