[백준] 30547 : Modified Gray Code

https://www.acmicpc.net/problem/30547

문제 분석

 문제 설명에 앞서 그레이 코드 개념에 대해 간단히 설명하겠다. 그레이 코드는 일반 이진 코드와 다르게 앞뒤 전후의 숫자와 1비트만 다르게끔 10진수를 2진 코드로 표현하는 방식이다. 연속적인 변화에서 단일 비트만 변경되므로 오료나 오차 체크용으로 주로 사용되는 방식이다.

10진 코드	이진 코드	그레이 코드
0	0000	0000
1	0001	0001
2	0010	0011
3	0011	0010
4	0100	0110
5	0101	0111
6	0110	0101
7	0111	0100
8	1000	1100

 문제는 이러한 그레이 코드를 변형하여 앞뒤 숫자와 단일비트가 아닌 짝수개의 비트만큼만 차이가 나도록 하는 modified gray code를 만드는 문제이다. 이때 짝수개의 비트만 다른 것은 여러개 나올수 있으니 아직 사용안한 값중 가장 작은 값(10진수 기준)을 쓰도록 구성한다. 문제 풀이자체는 비트연산을 사용한 간단한 브루트 포스 문제이므로 자세한 설명은 하단에서 하겠다.

10진 코드	modified 그레이 코드
0	00000
1	00011
2	00101
3	00110
4	01001
5	01010
6	01100
7	01111
8	10001

문제 해결 전략

 문제의 그레이코드는 10bit로 고정 크기라 bitset 라이브러리를 사용하였다. 문제에서 다음 그레이코드를 고려해야할 것은 2가지이다. 조건을 위해서 기존 그레이 코드에 특정 마스크와 XOR 연산을 하여 다음 그레이 코드를 만들되 해당 마스크에서 1인 비트가 0보다 큰 짝수개가 있는지 체크하고(조건 1) 연산을 한 수가 이미 사용한수인지 visited로 체크하였다.( 조건2) 기타 자잘한 출력이나 연산은 bitset의 기능을 활용하였다.

조건 1: 짝수개의 비트만 차이가 난다.
조건 2: 아직 사용하지않은 가장 작은 수여야 한다.

코드

#include <iostream>
#include <vector>
#include <bitset>


using namespace std;

int N, K;

int main()
{
    cin >> N;
    int visited[1024]={false};
    int graycode[1024]={0};
    int currentNum(0);
    int minNum(1024);
    visited[0]=true;

    for (int ind = 1; ind < 1024; ind++)
    {
        minNum=1024;
        for (int i = 0; i < 1024; i++)
        {
            int bitcnt=bitset<10>(i).count();
            if (bitcnt>0 && (bitcnt%2==0))
            {
                int tempNum = currentNum^i;
                if (tempNum<minNum){
                    if (!visited[tempNum]){
                        minNum=tempNum;
                    }
                }
            }
        }
        visited[minNum]=true;
        graycode[ind]=minNum;
        currentNum=minNum;
    }

    bitset<10> temp;
    vector<bitset<10>> answers;
    for (int i = 0; i < N; i++)
    {
        cin >> K;
        temp=graycode[K];
        answers.push_back(temp);
    } 
    
    for (size_t i = 0; i < N; i++)
    {
        cout << answers[i] << "\n";
    }
}