# 4779

칸토어 집합이라는 문제입니다. 문제에 대한 설명은 따로 진행하지 않고 오답노트를 기준으로 작성하겠습니다. 문제의 특성상, 재귀와 메모이제이션을 사용한다면 해결할 수 있는 것은 알았고 재귀에 대해서 먼저 고려했습니다.

 

재귀 함수

재귀로 풀 때, 어떤 부분에서 재귀를 둬야할지 고민을 했습니다. 

 

""" 재귀
3 : ---------------------------
2 : ---------         ---------
1 : ---   ---         ---   ---
0 : - -   - -         - -   - -
"""

처음에는 빈 공백이 3에서 2로 다운될 때, 3의 제곱만큼 공백이 있고 2에서 1로 다운될 때도 3의 1제곱만큼 공백이 있는 것을 확인하고 다음 포인트를 recursion case로 두면 된다고 생각했습니다.

 

공백을 생성해줄 때, 3의 n만큼의 제곱한 값을 - 값에 곱하여 문자를 먼저 만들었고 사이의 값을 슬라이싱을 통해 강제로 형태를 만들어주었습니다. 물론 문자열은 immutable하기 때문에 새로운 변수에 참조시켜 진행하였습니다. 하지만 문자를 만들었으나 이는 단순히 모양만 잡아주었을 뿐 재귀를 돌리기에는 정말 애매하게 되어버렸습니다. 그래서 재귀의 방식으로는 제 손으로 해결하지 못했습니다.

 

""" 메모이제이션
0 : -
1 : - -
2 : - -   - -
3 : - -   - -         - -   - -
"""

원래는 메모이제이션 용도로 만들어두었던 주석에서 모양을 발견할 수 있었습니다.

 

""" 메모이제이션
0 : -
1 : - -
2 : - -   - -
3 : - -   - -         - -   - -
"""

recursion(1) = recursion(0) + '공백' + recursion(0)
recursion(2) = recursion(1) + '공백' + recursion(1)
recursion(3) = recursion(2) + '공백' + recursion(2)

recursion 함수의 매개변수가 0일 때를 base case로 잡고 나머지를 recursive case로 조정하면 될 것 같았습니다. 추가적으로 공백을 구하는 식만 알면 됐는데 3의 매개변수 - 1만큼의 제곱을 공백에 곱해주면 된다는 것은 상위에서 추측할 수 있었습니다.

 

def recursion(n):
  if (n == 0):
    print('-', end="")
    return
  
  recursion(n - 1)
  print(' ' * (3 ** (n - 1)), end="")
  recursion(n - 1)
  
while True:
  try:
    n = int(input())
    recursion(n)
    print()
  except:
    break

 

메모이제이션

메모이제이션 방법은 DP를 가지고 정리했을 당시가 떠올라서 구현에는 어려움이 있지는 않았습니다.

 

""" 메모이제이션
0 : -
1 : - -
2 : - -   - -
3 : - -   - -         - -   - -

arr[0] = '-'
arr[1] = arr[0] + ' ' * (3 ** (1 - 1)) + arr[0]
arr[2] = arr[1] + ' ' * (3 ** (2 - 1)) + arr[1]
arr[i] = arr[i - 1] + ' ' * (3 ** (i - 1)) + arr[i - 1]
"""

점화식을 먼저 구할 수 있겠다는 생각이 들었습니다. 위의 주석에 있는 것처럼 이전 값을 꺼내 사용할 수 있는 부분을 찾아 점화식으로 만들었고 문제의 요구사항에 맞추어 코드를 구현하였습니다.

 

def memoization(n):
  MAX = 12
  arr = [' '] * (MAX + 1)
  arr[0] = '-'
  
  for i in range(1, MAX + 1):
    arr[i] = arr[i - 1] + ' ' * (3 ** (i - 1)) + arr[i - 1]

  return arr[n]


while True:
  try:
    n = int(input())
    print(memoization(n))
  except:
    break

문제에서 N은 12보다 작은 정수라고 하였습니다. 따라서 이 값은 하드코딩으로 처리하였습니다. 

 

정리

사실 재귀로 구현할 때는 30분이라는 시간을 투자하였으나 해결하지는 못했습니다. 하지만 메모이제이션으로 구현했을 때와 비교해보았는데 재귀를 너무 많이 생각하려고 하면 오히려 독이 된다는 것을 깨달았고 점화식처럼 사용하되 base case만 잘 구현해주면 될 것 같다는 생각이 들었습니다.