그레이 코드

2004 가을학기 문제해결기법	문제 #6

그레이 코드(Gray code) 열은 이진 코드의 열로써, 각 코드는 바로 앞의 코드와 오직 한 비트만 다르다는 성질이 있다. 마지막 코드는 맨 처음 코드와 한 비트만 다르다. 아래에 3-비트 그레이 코드 열이 있다.

이진수	000	001	010	011	100	101	110	111
그레이 코드 열	000	001	011	010	110	111	101	100

이진수를 그에 대응하는 그레이 코드로 바꾸어 주는 아주 간단한 알고리즘이 알려져 있다. 우선 예를 들어 설명하면, 이진수 011을 변화하기 위하여 먼저 이진수의 첫째 비트를 복사하여 첫째 비트 0을 얻고, 둘째 비트를 얻기 위해서 이진수의 첫째 비트와 둘째 비트를 더하여 1을 얻은 다음, 셋째 비트를 얻기 위해서 둘째 비트와 셋째 비트를 더한 값 10에서 올림수를 무시하고 오른쪽 비트만 취한다. 일반적으로 말하면, 그레이 코드의 첫째 비트는 이진수의 첫째 비트에서 얻고, 첫째 비트를 제외한 번째 비트는 이진수의 번째 비트와 번째 비트를 더한 다음 올림수를 무시하고 오른쪽 비트만을 취하여 얻을 수 있다.

이진수	그레이 코드
01110	01001
111111	100000
1001001	1101101
000111000	000100100

-비트 이진수를 그에 대응하는 -비트 그레이 코드로 변환하는 프로그램을 작성하시오. 프로그램 이름은 gray.cpp, 실행 파일의 이름은 gray.exe, 프로그램 설명 파일 이름은 gray.hwp로 하고, 프로그램의 실행시간은 1초를 초과할 수 없다.

입력 형식

입력 파일 input.txt는 두 줄로 이루어져 있고, 각 줄에는 정수가 하나씩 있다. 첫째 줄에 비트의 수 이 입력된다. 여기서, 이다. 둘째 줄에는 -비트 이진수를 나타내는 이진 스트링이 주어진다.

출력 형식

출력 파일 output.txt에 주어진 -비트 이진수에 대응하는 -비트 그레이 코드를 나타내는 이진 스트링을 출력한다.

입력과 출력의 예

입력(input.txt)

3

011

출력(output.txt)

010