lhw941   3년 전

기존 출력형식은 잘못되지 않았습니다. 문제에서 출력되는 문자의 종류는 N이 주어졌을 때 a1~aN 까지입니다. 물론 C(N,2)개의 문자가 출력되는건 맞지만 그건 올바른 답에서 일부 문자들이 중복해서 출력되기 때문입니다. 따라서 a_C(N,2) 같은 식의 표현은 옳지 않고 혼란을 줄 수 있습니다. 그리고 올바른 답은 항상 a1에서 시작해서 aN으로 끝납니다. 그래서 원래 출력형식을 " a1 a2 ... aN "이라고 써놓은거고요. 아래는 기존 문제의 원문입니다.


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개의 수가 서로 다름을 나타낼 때에는 C(5,2)=10 개의 쌍에 대하여 서로 다름을 표현해야 하고 이는 10개의 “!=”를 필요로 하기 때문이다. 일반적으로 주어진 N개의 수가 모두 다름을 한 줄 표기법으로 표현하는 데는, 적어도 C(N,2) 개의 “!=”이 필요함이 알려져 있다. (C(N,2) 는 N개의 서로 다른 대상 중 2개를 뽑는 가짓수이다.) 숫자 N이 주어졌을 때, 숫자 a1~aN 에 대하여 가능한 한 줄 표기법 중 가장 짧으면서 사전 순서로 가장 앞에 오는 한 줄 표기법을 출력하는 프로그램을 작성하라. 단 이 때 “!=”은 공백으로 대신하기로 한다.  (예를 들어 N=3이 주어졌을 때 a1 a2 a3 a1 는 정답으로 인정되지만 a3 a1 a2 a3 는 사전순서로 앞의 표기법보다 뒤에 오기때문에 올바른 한 줄 표기법이라도 정답으로 인정되지 않는다.)

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

 

<입력>

N(N은 1<N<500 인 홀수인 자연수)

<출력>

a1 a2 a3 ... aN

시간제한: 1초

메모리제한: 1GB

<입력 예시1>

3

<출력 예시1>

a1 a2 a3 a1

<입력 예시2>

5

<출력 예시2>

a1 a2 a3 a1 a4 a2 a5 a3 a4 a5 a1


jh05013   3년 전

출력 형식의 a1, a2 등을 정확히 그 문자로 해석하면 "a1 a2 a3 ... aN"은 a1부터 aN까지 차례대로 출력하라는 뜻이 됩니다. 또한 답은 aN이 아닌 a1으로 끝납니다.

가장 맞는 표현은 a(b0) a(b1) ... a(bC(N,2))인 것 같습니다.

doju   3년 전

"올바른 답은 항상 a1에서 시작해서 aN으로 끝납니다." - 예시만 봐도 그렇지 않네요.

"a1 a2 ... aN"이라는 표기는 아무리 봐도 a1부터 aN까지를 순서대로 출력하라는 뜻으로밖에 안 보입니다. 입출력 조건을 기호나 수식으로 모두가 명확히 알 수 있게 표현할 수 없다면 그냥 글로 풀어 쓰는 것은 어떨까요?

아래와 같이 수정하는 것을 제안해 봅니다.


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

출력

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

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