[C++] [CSES] Grey Code (Introductory Problems)

CSES의 열 세번째 문제입니다.

문제를 이해 못해서 끙끙대다가 해답을 보고 만.. 그런 문제입니다.

 

Task

A Gray code is a list of all 2^n bit strings of length n, where any two successive strings differ in exactly one bit (i.e., their Hamming distance is one).

Your task is to create a Gray code for a given length n.

Input

The only input line has an integer n.

Output

Print 2^n lines that describe the Gray code. You can print any valid solution.

Constraints

• 1≤n≤16

Example

Input:
2

Output:
00
01
11
10

 

Code

#include<bits/stdc++.h>
using namespace std;
int n;
void grey(int n){
    vector<string> v = {"0", "1"};
    vector<string> cur;
    for (int i=1;i<n;i++){

        for (string c : v){
            cur.push_back("0" + c);
        }
        reverse(v.begin(), v.end());
        for (string c : v){
            cur.push_back("1" + c);
        }
        v.clear();
        v = cur;
        cur.clear();
    }
    for (string s : v){
        cout << s << "\n";
    }
}
int main(){
    cin >> n;
    grey(n);
}

생각해야 하는 것

• n = 1 :                            0 | 1
• n = 2 :                    00 01 | 11 10
• n = 3 : 000 001 011 010 | 101 111 110 100
• 위 과정을 일반화한다면  0 : f(n-1) | 1 : ~f(n-1) 꼴로 나타납니다. 즉, 현재의 문자열에 0을 붙인 것이 왼쪽, 뒤집어서 1을 붙인 것이 오른쪽으로 가게 됩니다. 1 -> 2의 과정은 다음과 같습니다.
• n = 1 :                            0 | 1
• n = 2 :                    00 01 | 11 10
• 솔직하게 말씀드리자면 해당 문제에서 grey code 설명만 듣고 방법을 떠올리는 것이 굉장히 어려운 것이라고 느꼈습니다.
• n = 3 케이스까지 주었다면 재귀적인 규칙이 있다는 것을 알 수 있었을 것 같습니다...!