본문 바로가기

BAEKJOON/수학

백준 4779번 [칸토어 집합](C++) -yes6686- 티스토리

728x90
SMALL

백준 문제 풀이: 4779 [칸토어 집합]


문제 링크: https://www.acmicpc.net/problem/4779

문제 설명:

칸토어 집합은 0과 1 사이의 모든 실수로 구성된 집합으로, 다음과 같은 방식으로 재귀적으로 정의됩니다:

  • 0단계에서 칸토어 집합은 "-" 입니다.
  • n단계에서 칸토어 집합은 n-1단계의 칸토어 집합 좌우에 각각 n-1단계 칸토어 집합을 추가하고 가운데는 공백으로 대체하여 생성합니다.

예를 들어, 2단계 칸토어 집합은 다음과 같습니다:

"- -   - -"

입력으로 n이 주어질 때, n단계의 칸토어 집합을 출력합니다.


문제 해결 코드


#include <iostream>
using namespace std;

string dp[13];

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

    dp[0] = "-"; // 0단계 칸토어 집합 초기화
    for (int i = 1; i <= 12; i++) {
        dp[i] += dp[i - 1]; // 좌측 칸토어 집합 추가
        for (int j = 0; j < dp[i - 1].size(); j++) {
            dp[i] += " "; // 중간 공백 추가
        }
        dp[i] += dp[i - 1]; // 우측 칸토어 집합 추가
    }

    int n;
    while (cin >> n) {
        cout << dp[n] << '\n'; // n단계 칸토어 집합 출력
    }
    return 0;
}

예제

입력:
0
1
2

출력:
-
- -
- -   - -

코드 설명

  • 동적 프로그래밍: `dp[i]`를 이용해 i단계의 칸토어 집합을 저장합니다.
  • 재귀적 정의 구현: 이전 단계의 칸토어 집합을 좌우로 복사하고, 가운데는 공백으로 대체합니다.
  • 출력: 입력으로 주어진 n단계의 칸토어 집합을 출력합니다.

시간 복잡도

  • 칸토어 집합 생성: O(n ⋅ 3^n) (3^n 크기의 문자열 생성 및 복사)
  • 출력: O(3^n)

결과

위 코드는 주어진 입력에 따라 정확히 n단계의 칸토어 집합을 출력합니다. 메모리를 활용한 동적 프로그래밍 방식으로 효율적으로 구현되었습니다. 개선점이나 다른 접근 방식에 대한 논의는 환영합니다!

728x90
LIST