[백준] 4779 - 칸토어 집합

1. 문제

4779번: 칸토어 집합

2. 개요

칸토어 집합은 0과 1사이의 실수로 이루어진 집합으로, 구간 [0, 1]에서 시작해서 각 구간을 3등분하여 가운데 구간을 반복적으로 제외하는 방식으로 만든다.

‘-’ 가 3^N개 있는 문자열로 칸토어 집합의 근사를 만들어 출력하는 문제.

3. 풀이 및 코드

3-1. 풀이

시작점부터 1/3까지를 구역1, 1/3부터 2/3까지를 구역2, 2/3부터 마지막까지를 구역3 이라고 하자.

구역 2를 모두 공백문자로 바꾸는 작업 action을 수행한다.

이 작업 action을 구역1의 구역2에 대해 진행하고 구역3의 구역2에 대해 진행하고 … 를 반복한다.

작업을 마치고 답을 출력한다.

3-2. Python

import sys

while True:
    N = sys.stdin.readline().rstrip()

    if N == "":
        break

    N = int(N)

    S = list(3 ** N * '-')

    def action(s, e):
        if s + 1 == e:
            return

        for i in range(s + (e-s) // 3, s + (e-s) * 2 // 3):
            S[i] = ' '

        action(s, s + (e-s) // 3)
        action(s + (e-s) // 3 * 2, e)

    action(0, 3 ** N)
    print(''.join(S))

3-3. C#

namespace boj_4779
{
    internal class Program
    {

        static char[] S;

        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            while (true)
            {
                string input = sr.ReadLine();

                try
                {
                    int N = int.Parse(input);

                    S = new char[(int)MathF.Pow(3, N)];
                    Array.Fill(S, '-');

                    action(0, (int)MathF.Pow(3, N));
                    sw.WriteLine(string.Join("", S));
                    sw.Flush();
                }

                catch(Exception)
                {
                    sw.Close();
                    break;
                }
            }
        }

        static void action(int s, int e)
        {
            if (s + 1 == e)
                return;

            for (int i = s + (e - s) / 3; i < s + (e - s) * 2 / 3; i++)
                S[i] = ' ';

            action(s, s + (e - s) / 3);
            action(s + (e - s) * 2 / 3, e);
        }
    }
}