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
'BAEKJOON > 수학' 카테고리의 다른 글
백준 32929번 [UOS 문자열](C++) -yes6686- 티스토리 (0) | 2025.01.03 |
---|---|
백준 4030번 [포켓볼](C++) -yes6686- 티스토리 (0) | 2024.12.31 |
백준 32951번 [AI 선도대학](C++) -yes6686- 티스토리 (0) | 2024.12.30 |
백준 11444번 [피보나치 수 6](C++)-yes6686- 티스토리 (0) | 2024.12.29 |
백준 10830번 [행렬 제곱](C++)-yes6686- 티스토리 (0) | 2024.12.29 |