[C#] 백준 18222 투에-모스 문자열

https://www.acmicpc.net/problem/18222

 

투에 모스 문자열로 이전단계를 계속 붙여서 01이 계속 늘어나는 수이다.

 

X1 = X + X의 반대

X2 = X1 + X1의 반대

 

이런식으로 앞의 문자 배열과 그 역이 합쳐진 수열이 바로 투에 모스 문자열이다.

 

 

시간초과코드 오답

using System;

class Program
{
    static void Main()
    {

        var k = long.Parse(Console.ReadLine());

        // 결과 출력
        Console.WriteLine(Calculate(k - 1));

    }

    static char Calculate(long k)
    {
        if (k == 0) return '0'; // 첫 번째 문자는 항상 '0'

        long length = 1;
        while (length * 2 <= k + 1)
        {
            length *= 2;
        }

        if (k < length) // k가 첫 번째 절반에 속하면
        {
            return Calculate(k);
        }
        else // k가 두 번째 절반에 속하면
        {
            return Calculate(k - length) == '0' ? '1' : '0';
        }
    }

}

 

이렇게 생각했다 X1은 X와 X의 반대 즉, 이전 배열 두개를 붙인걸 반으로 나눠서 이 이상 넘어가면 0 아니면 1 이런식으로 재귀를 이용해 보았다.

 

하지만 이는 시간초과로 인해 해결되지 못했다.

 

투에-모스 문자열

그래서 투에-모스 문자열에 대해 찾아봤더니, 해결하는 방법에는 n번째 원소를 계산하기 위해서는 n을 이진수로 써야 한다고 한다. 그리고 n의 이진 에서 1의 개수가 홀수면 1, 짝수면 0이라고 한다. (출처 - 위키백과 투에-모스 수열)

 

그래서 숫자 k를 받았다면, 이를 나머지 계산으로 2를 계속 나눠서 1이 나오는 개수만큼 count를 증가시키고, 다 계산했다면 count를 다시 2로 나눠서 1이 나오면 1, 0이 나오면 0을 출력해주면 된다.

 

정답

using System;

class Program
{
    static void Main()
    {
        // 입력 받기
        long k = long.Parse(Console.ReadLine());
        k-= 1;

        int count = 0;

        // 1의 개수를 계산
        while (k > 0)
        {
            count += (int)(k % 2); // 1의 개수 증가
            k /= 2; // k를 2로 나눔
        }

        // 결과 출력 (1의 개수의 홀짝성)
        Console.WriteLine(count % 2);
    }
}