4779번: 칸토어 집합

 

- 문제 사이트: https://www.acmicpc.net/problem/4779

4779번: 칸토어 집합

 

주어진 문자열을 삼등분하여 두번째 섹션에 공백을 주고, 이를 공백의 길이가 1이 될 때까지 반복해주는 문제이다.

이 때, 입력 조건 (while문 유지 조건)은 N을 입력 받는 동안 (cin >> N)으로 설정해주도록 한다.

 

1) 횟수 입력 받음: N

2) 전체 문자열의 길이 확인: 3^N

3) 전체 문자열을 세 구간으로 나눈 후 가운데 구간을 빈 값 (' ')으로 대체

4) 첫번째 구간과 세번째 구간에 3)번 로직 적용

5) 나눈 구간 길이가 1이 될 때까지 반복

 

#include <iostream>
#include <string>
#include <cmath>
using namespace std;

void change(string& origin, int length, int start)
{
    if (length == 1)
    {
        for (int i = start + 1; i < start + 2; i++)
            origin[i] = ' ';
        return;
    }

    length /= 3;
    for (int i = start + length; i < start + length * 2; i++)
        origin[i] = ' ';

    change(origin, length, start);
    change(origin, length, start + length * 2);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    while (cin >> N)
    {
        int length = pow(3, N);
        string origin = string(length, '-');

        change(origin, length, 0);
        cout << origin << endl;
    }
    return 0;
}

- 메모리: 2848 KB

- 시간: 4 ms

- 코드 길이: 747 B