아주 사악한 그래프 문제
면접 대비시간 제한2초메모리 제한512 MB
길이가 가장 짧으면서 사전순으로 가장 앞서는 길이 2^N+N-1의 이진 문자열을 구합니다. 여기에는 길이 N인 모든 이진 수가 부분 문자열로 포함됩니다.
문제
프로그래밍 올림피아드 문제의 지문은 왜 이렇게 엉뚱한 모험으로 가득 차 있고, 온갖 우스꽝스러운 사건으로 넘쳐나는 걸까? 이 문제의 지문도 그렇게 쓰고 싶다. 하지만 지금 내가 쓰려는 이야기는 이 작은 종이에 담기에는 너무 클 것이 분명하다. 그렇다면 "계속 쓸까? 어떻게 할까?" 사실 꽤 흥미롭다. 한번 읽기 시작하면 문제 푸는 것도 잊고 재미있게 끝까지 읽게 될 거라고 장담할 수 있을까? 이 이야기가 뭐라고 이렇게까지 소란을 피우는 걸까? 문제와 이야기 중 어느 쪽이 중요한가? 어느 쪽을 고를 것인가? 라고 생각하는가? "질문이 왜 이렇게 많아. 하나만 물어봐." :)) 아니면 이 이야기는 도대체 뭐가 이렇게 쓸데없이 길게 늘어놓았냐고? 왜 진짜 지문이나 제대로 쓰고 일을 안 하냐고 생각하는가? "뭐 어쩌겠어. 다들 그렇게 살지."
문제 요약 지문: N자리 이진수를 모두 포함하는 가장 짧은 문자열을 사전순으로 가장 앞선 것을 출력하라.
입력
첫째 줄에 테스트의 수 T (T ≤ 15)가 주어진다. 다음 줄부터 각 줄에 하나의 테스트를 나타내는 자릿수 N (N ≤ 15)이 주어진다.
출력
각 테스트에 해당하는 답을 새 줄에 출력한다.
힌트
이진수를 N자리로 만들기 위해 0으로 시작한다. 예를 들어 3자리 이진수를 나열하면 000, 001, 010, 011, 100, 101, 110, 111이고, 이들을 모두 포함하는 가장 짧은 문자열 중 사전순으로 가장 앞선 것은 0001011100이다.