이진 암호화 [0970 / 03CA] 
Time Limit(Test case) : 1000(ms)Number of users who solved : 81 Total Tried : 128
The Champion of this Problem (C++) : gs17007 - 0ms / 489byte
My Best Submission (C++) : N/A
[JKJeong 2014]
Background
이진 압축이란 {0, 1}로 이루어진 길이가 2^k인 문자열에 대해서, 모두 같은 문자가 될 때까지 크기가 2^(k-1)인 두 그룹으로 분할하여 모두 같은 문자가 되도록 하는 과정으로 암호화를 한다.만약 주어진 원문이 길이가 4인
0000
라면, 암호문은
0
이다.
만약 주어진 암호문이 길이가 4인
1101
이라면 모든 문자가 같지 않기 때문에
11 01
로 일단 한 번 분할하고
다시 뒷 부분은 01로 같지 않으니
11 0 1
로 분할한다.
즉 이로써 만들어진 암호문은
-1-01
이 된다.
-1-01의 의미는
- : 먼저 전체를 분할하고
1 : 분할된 왼쪽 부분은 모두 1이고
- : 오른쪽 분할은 다시 분할하며,
01 : 분할된 결과는 0과 1이라는 의미이다.
길이가 n인 원문을 입력받아서 암호문을 출력하는 프로그램을 작성하시오.
Input
첫 번째 줄에 암호문의 길이 n이 입력된다.두 번째 줄에 길이가 n인 0, 1로 구성된 암호문이 입력된다.
[입력값의 정의역]
1 <= n <= 2^18 (단, n은 모두 2^k (k는 음이 아닌 자연수))
Output
위 원리로 만들어진 암호문을 출력한다.IO Example
입력4
0000
출력
0
입력2
4
1101
출력2
-1-01
Prob Analysis : [Problem Statistics] | [Solution]