[BOJ 18222 투에-모스 문자열]을 이진법을 이용해 풀어보자

문제 읽기

문제 원문 링크 바로가기

 문제 내용을 읽어보면, 뭔가 알 수 없는 주기로 반복되거나 뒤집히는 문자열이 무한히 이어질 때, 특정한 자리 k에 오는 숫자가 0인지 1인지를 알아내는 문제라는 걸 알 수 있다.

 문제를 이해하는 건 어렵지 않지만, 난해한 규칙을 기반으로 연장되는 무한한 문자열을 어떻게 구성해야할지가 상당히 고민되는 문제이다. 정말로 10의 18승만큼 투에-모스 문자열을 나열할 수도 없는 노릇이니... 어떻게 규칙을 통해 k번째자리 숫자를 알아내야할까? 라는 것이, 이 문제를 처음 보았을 때가 내가 고민한 문제였다.

결론 미리보기

 다른 풀이를 찾아보았거나 풀어보았다면 알겠지만, 이 문제의 풀이 코드는 생각보다 간단한 편이다. 나의 풀이를 간단하게 정리해 결론부터 말해보자면, 다음과 같다.

1. 자연수 k에서 1을 뺀 후
2. 그 값을 이진수로 변환해
3. 이진수에서 나타난 1의 개수가 홀수면 1, 짝수면 0이다.

 뜬금없이 웬 이진수? 싶을수도 있겠다. 지금부터 왜 이런 결론이 나게 되었는지에 대해 천천히 설명해보도록 하겠다.

어떻게 반복되고 있는가?

 투에-모스 문자열은 길이 1의 문자열("0")부터 시작해, 전체 문자열을 반전해 뒤에 가져다 붙이는 식으로 반복되며 갱신이 된다. 그렇다면, 어떤 반복이 되고 있는지를 알아보는 게 규칙을 알아내기 위한 첫걸음일 것이다.

가장 첫번째 문자열을 1번이라고 했을 때, 16번까지 적었을 때의 투에-모스 문자열은 다음과 같다.

글씨가 왜 점점 오른쪽 위로 올라가는거지...??

 이렇게 보면 단순한 0과 1의 나열이라고 보일 수도 있지만, 이 문자열을 반전 후 이어붙여지는 단위로 잘라보면 이렇게 된다.

1-2-4-8-16 순으로 점점 늘어나는 투에-모스 문자열

 2번 자리에 있는 "1"은, 1번 자리의 "0"이 반전되어 붙은 결과이다. 또, 3번과 4번 자리의 "10"은, 1번과 2번 자리의 "01"이 반전되어 붙은 결과이다. 똑같은 방식으로, 5~8번 자리의 "1001"은, 1~4번 자리의 "0110"이 반전되어 붙은 결과이다.

 여기까지는 문제 원문에서 알 수 있는 정보와 완전히 같다. 그렇다면, 이번에는 관점을 바꿔서, 특정 자리의 숫자가 어떤 숫자가 반전된 결과인지를 알아보자. 예시로, 8번 자리에 있는 "1"을 따져보았다.

8 → 4 → 2 → 1 순으로 전개된다!

 8번 자리를 반전 기준으로 나열하면, 다음과 같다.

• 8) 1~8 범위의 1~4 / 5~8 기준으로 보았을 때 => 8번 자리는 4번 자리의 반전값
• 4) 1~4 범위의 1, 2 / 3, 4 기준으로 보았을 때 => 4번 자리는 2번 자리의 반전값
• 2) 1~1 범위의 1 / 2 기준으로 보았을 때 => 2번 자리는 1번 자리의 반전값

수학적 안목이 뛰어나진 않아서, 이 이상의 체계적인 설명은 조금 어렵지만... 간격을 보면, 각 숫자의 자리는 자기자신보다 작으면서 가장 큰 2의 제곱수만큼 떨어진 자리의 값을 반전한 값이라는 걸 알 수 있다. 반복되는 패턴이 2의 제곱수마다 전개되기 때문인 것으로 보인다.

 위에 나열한 3가지 조건을 8의 관점에서 다시 정리해보면, 다음과 같다.

8번 자리 = 4번 자리의 반전 = 2번 자리 = 1번 자리의 반전 = "0"의 반전 = 1

 우리는 첫번째 자리의 값이 "0"이라는 걸 확실하게 알고 있으므로, 1이 남을 때까지, 자기자신보다 작으면서 가장 큰 2의 제곱수만큼 떨어진 자리를 계속해서 구해나가면, 1의 자리값인 "0"으로부터 몇 번 반전되었는지를 알 수 있다. 결국, 이 문제의 시점을 이렇게 바꿀 수 있는 것이다 : k번째 자리의 숫자는, 첫번째 자리의 숫자로부터 몇 번 반전되었는가? 이것을 알기 위해서는, '자기자신보다 작으면서 가장 큰 2의 제곱수'가 몇 번이 빠져야, 1이 남는지를 알아야 한다.

 또 다르게 말해보자면, (k-1) 이라는 숫자를 2^p+2^q+2^r+... (이때 p, q, r은 자연수)로 표현한 후, 나온 2의 제곱수의 개수를 세면 된다는 것이다.

 그런데, 2^p+2^q+2^r+... 같은 수의 표현, 어디서 본 적 있지 않나?

야! 이거 이진법이다!

 우리가 평소에 사용하는 10, 20, 253... 등의 평범한 숫자는 십진수로 이루어져있는 숫자다. 십진수란, 각 자리의 숫자를 10의 제곱수로 나타낸 숫자이다. 예를 들어 숫자 2024가 있다면, 이 숫자는 2*10^3+2*10^1+4*10^0 로 분해해서 10의 제곱수로 표현할 수 있다. 각 자릿수별 단위가 10이기 때문에, 각 자릿수마다 올 수 있는 계수는 0에서 9 사이의 값이 된다.

 십진수 다음으로 자주 쓰이는 진법은, 이진수다. 이진수란 2의 제곱수의 합으로 숫자를 나타내는 방식이다. 즉, 위에서 보았던 2^p+2^q+2^r+... 같은 형태는 이진수의 형태와 일치한다!

 위의 예시를 다시 이진법을 이용해 표현하면 다음과 같이 된다.

  k-1의 값인 7을 이진수로 표현했을 때, 1의 개수는 총 3개(111)이다. k-1이 2의 제곱수 3개가 합쳐서 구성된다는 뜻으로, 이 문제에서는 k번째의 자리, 8번째 자리가 1번째 자리로부터 3번 반전되었다는 것과 같은 의미이다. 반전의 반전은 반전되지 않은 것과 같은 의미이므로, 짝수 수만큼의 반전된 횟수는 상쇄된다. 즉, 1번째 자리의 반전, "1"이 8번째 자리의 값이라는 것을 알 수 있다.

 이제 결론을 다시 복기해보겠다!

1. 자연수 k에서 1을 뺀 후
2. 그 값을 이진수로 변환해
3. 이진수에서 나타난 1의 개수가 홀수면 1, 짝수면 0이다.

 k-1을 이진수로 표현한 건, 1번째 자리로부터 몇 번 반전되었는지를 세기 위함이었다. 덧붙여, 개수가 홀수면 1이고 짝수면 0이기 때문에, 2로 나눈 나머지를 그대로 답으로 출력해도 된다.

코드

이하는 실제로 문제 풀이에 제출한 코드이며, Java 8로 작성되어있다.

import java.util.*;
import java.io.*;

public class Main {

	public static void main(String[] args) throws Exception {
		/* 입출력 관련 객체 작성 */
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		/* [풀이 전략]
		 * 결국 어느 단위로 뒤집어지느냐가 문제다...
		 * 1, 2, 4, 8, ... 단위로 뒤집어지고 있기 때문에, K보다 작으면서 가장 큰 2의 제곱수를 한 번 빼 주면, 해당 자리의 반전이라는 계산이 나온다.
		 * 아... 아무튼 열심히 생각해봤는데, K-1을 이진수로 변환했을 때, 1의 개수가 짝수면 0이고 홀수면 1이다.
		 * 맞...았으면 좋겠는데 자신은 없다...
		 * */
		
		// 첫번째 줄 : k가 바로 입력된다
		// 10^18까지 들어오므로, long으로 받는다
		long K = Long.parseLong(br.readLine());
		
		// 입력받기 종료
		// K-1을 이진수로 변환했을 때 1의 개수를 센다
		// 이진수로 변환한 값은 필요없고, 1의 개수만 있으면 되므로 K를 직접 줄인다.
		K--;
		int oneCount = 0;
		while(K > 1) {
			long mok = K/2;
			long remained = K%2;
			if(remained == 1) {
				oneCount++;
			}
			K = mok;
		}
		// K가 1이라면 그것도 oneCount에 넣는다
		if(K == 1) oneCount++;
		
		if(oneCount%2 == 0) {
			System.out.println(0);
		} else System.out.println(1);

	}

마치며

 어떻게든 혼자서 문제를 풀어낸 후 다른 풀이들을 많이 봤는데, 이진수로 변환한 후에 풀이하는 방법에 대한 글은 많지 않은 것 같아 한 번 작성해보았다. 논리도약이 많은 글이긴 하지만, 누군가에게 도움이 된다면 기쁠 것 같다!