BOJ 4848 - 집합 숫자 표기법

문제

자연수를 집합 표기법으로 나타낸다. 0은 {}, 1은 {{}}, 2는 {{},{{}}} 등이다. 두 집합 숫자의 합을 집합 표기법으로 출력하라.

입력

테스트 케이스 수 T와 각 케이스마다 두 집합 표기법 문자열이 주어진다.

출력

각 케이스마다 두 수의 합을 집합 표기법으로 출력한다.

예제

입력	출력
`1` `{{}} {{}}`	`{{},{{}}}`

풀이

0부터 15까지의 집합 표기법을 미리 생성하고, 입력을 매칭하여 합을 출력한다.

DP로 0~~15의 집합 표기법 문자열을 생성한다. DP[i]는 0~~i-1까지의 모든 표기를 쉼표로 연결하고 중괄호로 감싼다
입력 문자열을 DP 배열과 비교하여 정수값을 역산한다
두 수의 합에 해당하는 DP 값을 출력한다

핵심 아이디어: 폰 노이만 순서수 표기법으로, n = {0, 1, ..., n-1}의 재귀적 구조를 이용하여 미리 테이블을 구성한다.

코드

#include <iostream>
 
using namespace std;
 
int main(void)
{
  int T = 0;
  string DP[16];
  string str1;
  string str2;
 
  cin >> T;
 
  DP[0] = "{}";
  DP[1] = "{{}}";
  DP[2] = "{{},{{}}}";
 
  for (int i = 3; i < 16; i++)
  {
    DP[i] = '{';
 
    for (int j = 0; j < i; j++)
    {
      DP[i] += DP[j] + ",";
    }
 
    DP[i].at(DP[i].size() - 1) = '}';
  }
 
  for (int t = 0; t < T; t++)
  {
    cin >> str1 >> str2;
    int num1 = 0, num2 = 0;
 
    for (int i = 0; i < 16; i++)
    {
      if (str1 == DP[i])
        num1 = i;
      if (str2 == DP[i])
        num2 = i;
    }
 
    cout << DP[num1 + num2] << endl;
  }
 
  return 0;
}

복잡도

시간: O(T * L) (L: 최대 표기법 문자열 길이)
공간: O(L)

문제