백준 문제 풀이

[BOJ :4779] 칸토어 집합

Koa

Jul 29, 20242y ago

문제 번호

Empty

문제 요구 사항

•

N번째 칸토어 집합의 근사를 출력한다.

해설

일단, N번째 칸토어 집합을 DP[n]이라 하자. 이때 아래의 식이 성립한다.

1. DP[0] = "-"

2. DP[n] = DP[n - 1] + (3 ^ (n - 1) 개의 공백) + DP[n - 1]

최대 N은 12이기 때문에 최대 문자열의 길이는 3^12 = 531,441이다.

따라서, 직접 문자열을 저장만 잘 반복없이 한다면 충분히 다 담아낼 수 있다.

코드

DP = ["" for _ in range(13)]

def f(n : int) -> str:
  """N 번째 칸토어 집합의 근사를 출력하는 함수"""

  if DP[n] != "":
    # N 번째 칸토어 집합이 이미 계산되어 있다면, 해당 값을 반환
    return DP[n]
  
  # N 번째 칸토어 집합을 계산하고 저장
  DP[n] = f(n - 1) + " " * (3 ** (n-1)) + f(n - 1)
  
  return DP[n] # N 번째 칸토어 집합 반환


DP[0] = "-" # 0 번째 칸토어 집합은 "-" 로 초기화
  
while 1:
  # 파일의 끝에서 입력을 멈추기 위한 무한 루프 및 예외처리
  try:
    n = int(input()) # N 입력
  except:
    break
  
  print(f(n)) # N 번째 칸토어 집합 출력

Subscribe to 'koa'

Subscribe to my site to be the first to receive notifications and emails about the latest updates, including new posts.
Join Slashpage and subscribe to 'koa'!