[백준/C++] 4779번 칸토어 집합

문제 해석

---

---

문제 풀이

---

보자마자 분할 정복인 것은 알았으나 분할정복을 제대로 이해하고 있지 않아서 선으로 문자열을 먼저 만들고 지워나가는 형식으로 구현하려고 했으나 어려워서 헤맸다. (개인적으로 분할정복이 제일 어렵다)

 

이 문제는 아래와 같은 패턴이다.

1. N == 2는 N == 1을 2번 더하고 사이에 N==1 만큼의 공백이 있고 N==1은 N==0을 2번 더하고 사이에 공백이 N==0
   만큼 존재한다.
2. 따라서 이전 것을 그리고 이전 사이즈만큼 공백을 그리고 이전 것을 그려주는 형식으로 분할하면 되는 문제이다.
3. 정복할 때는 N == 0인 초기상태일 때 '  -  ' 를 그린다.

---

코드

---

 

#include<bits/stdc++.h>
using namespace std;
int N ;

void Div_Con(int n) {

    int str_sz = pow(3, n - 1) ;

	if (n == 0)
    {
		cout << "-";
		return;
	}

	Div_Con(n - 1) ;
	for (int i = 0 ; i < str_sz ; i++)
		cout << " " ;
	Div_Con(n - 1) ;

}

int main()
{
    while(cin >> N)
    {
        Div_Con(N) ;
        cout << "\n" ;
    }
}

---

느낀점: 분할정복 드릅게 어렵다. 그리디랑 dp는 점화식과 패턴을 못찾겠고 분할정복은 구현을 못하겠다..

참조: https://beginnerdeveloper-lit.tistory.com/141

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

4779번: 칸토어 집합