\(n\)비트 반사 이진 그레이 코드(reflected binary Gray code)는 \(2^n\)개의 서로 다른 \(n\)비트 이진 문자열을 나열한 것으로, 다음 조건을 모두 만족한다.

• 첫 번째 문자열은 \(\underbrace{00\cdots0}_{n}\)이다.
• 연속한 두 문자열은 정확히 한 비트만 다르다.
• 마지막 문자열과 첫 번째 문자열도 정확히 한 비트만 다르다 (순환 성질).

표준 반사 이진 그레이 코드에서 \(i\)번째 (\(0\)부터 시작) 문자열은 정수 \(i \oplus \lfloor i / 2 \rfloor\)를 \(n\)비트 이진수로 나타낸 것이며, 이 나열은 유일하다. (\(\oplus\)는 비트별 XOR.)

\(n\)이 주어지면 이 \(n\)비트 그레이 코드 수열을 출력하여라.

\(1 \le n \le 16\).

첫째 줄에 정수 \(n\)이 주어진다.

\(2^n\)개의 줄에 걸쳐 \(n\)비트 그레이 코드를 차례대로 출력한다. 각 줄은 정확히 \(n\)자리의 이진 문자열(\(0\)과 \(1\)로만 이루어진)이어야 한다.

riseoj 작성

출처 Original