hanzch   1년 전

Gray 코드

시간 제한 메모리 제한
1 초 128 MB

문제

이진수는 2진법으로 표현된 수이며, 각 자릿수 또는 비트는 2의 거듭제곱의 가중치를 가집니다. 예를 들어, 십진수 23은 이진수로 10111로 표현됩니다:

(1 × 24) + (0 × 23) + (1 × 22) + (1 × 21) + (1 × 20) = (1 × 16) + (1 × 4) + (1 × 2) + (1 × 1) = 23

Gray 코드 수열은 이진수 값들의 수열로, 각 값은 바로 이전 값과 단 하나의 비트만 다릅니다. 다음 예시는 3비트 이진수의 표준 Gray 코드 수열을 보여줍니다.

이진 수열 000 001 010 011 100 101 110 111
표준 Gray 코드 수열 000 001 011 010 110 111 101 100

이진수를 표준 Gray 코드 값으로 변환하는 매우 간단한 알고리즘이 있습니다. 예를 들어, 이진수 011을 변환하려면 첫 번째 비트를 복사하는 것으로 시작합니다:

0 1 1
v    
0    

두 번째 비트를 얻기 위해, 주어진 이진수의 첫 번째와 두 번째 비트를 더해 합 0 + 1 = 1을 얻습니다:

0 + 1 1
    v  
0   1  

세 번째 비트를 얻기 위해, 두 번째와 세 번째 비트를 더해 합 1 + 1 = 10(이진수)을 얻지만, 올림수는 버리고 합의 가장 오른쪽 비트인 0만 취합니다:

0 1 + 1
      v
0 1   0

따라서 우리의 답은 010입니다.

일반적으로, 첫 번째 비트를 제외하고, 표준 Gray 코드의 k번째 비트는 주어진 이진수의 (k-1)번째 비트와 k번째 비트를 더하고 올림수를 버림으로써 얻습니다. 올림수를 버리는 덧셈 연산은 다음과 같이 완전히 설명될 수 있습니다:

  0    0    1    1
+ 0  + 1  + 0  + 1
---  ---  ---  ---
   0   1    1    0
---  ---  ---  ---

다른 예로, 5비트 이진수 10101은 위의 알고리즘을 적용하여 표준 Gray 코드 값 11111로 변환됩니다. 아래 표는 몇 가지 더 예시를 보여줍니다.

이진수 값 해당하는 표준 Gray 코드 값
01110 01001
11111 10000
10010 11011
10110 11101
00000 00000
10010 11011

당신은 n비트 이진수를 해당하는 n비트 표준 Gray 코드 값으로 변환하는 프로그램을 작성해야 합니다. 여기서 1 ≤ n ≤ 20 입니다.

입력

입력은 두 줄로 구성되며, 각 줄은 하나의 정수를 포함합니다.

  1. 첫 번째 줄은 비트 수를 나타내는 정수 n을 포함합니다 (1 ≤ n ≤ 20).
  2. 두 번째 줄은 n비트 이진수를 나타내는 길이 n의 비트 문자열을 포함합니다.

출력

출력은 주어진 n비트 이진수에 해당하는 표준 Gray 코드를 나타내는 길이 n의 비트 문자열을 포함합니다.

예제 입력 1

3
011

예제 출력 1

010

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