반응형
문제
https://www.acmicpc.net/problem/4779
4779번: 칸토어 집합
칸토어 집합은 0과 1사이의 실수로 이루어진 집합으로, 구간 [0, 1]에서 시작해서 각 구간을 3등분하여 가운데 구간을 반복적으로 제외하는 방식으로 만든다. 전체 집합이 유한이라고 가정하고,
www.acmicpc.net
풀이
가운데 문자열을 공백으로 바꿔줄 때, 몇개의 공백이 들어가는지 확인해봅시다.
n이 3일 때, 가운데 공백이 $3^2 = 9$개가 들어가게 됩니다.
n이 2일 때는 $3^1 = 3$개가 들어가네요.
즉, 공백은 n에 따라서 $3^{n-1} 개$가 들어가네요.
재귀함수로 접근을 해서 풀어줍시다.
n이 0이라면 "-"를 return 해줍시다.
n이 0보다 크다면, 공백을 $3^{n-1}개 앞뒤로 n - 1에서 나타나는 패턴을 붙혀주는 식으로 구해줍시다.
재귀함수로 n이 0이 될 때까지, 이 패턴을 반복하게 되면 원하는 답을 구할 수 있습니다.
소스코드
후기
출력해야할 선의 패턴을 쪼개고 어떻게 합쳐줄지 생각해보고 재귀를 떠올렸습니다.
반응형
'PS > 백준' 카테고리의 다른 글
| [BOJ] 백준 10157 자리배정 (Swift) (0) | 2023.03.31 |
|---|---|
| [BOJ] 백준 1343 폴리오미노 (Swift) (0) | 2023.03.31 |
| [BOJ] 백준 13909 창문 닫기 (Swift) (0) | 2023.03.27 |
| [BOJ] 백준 15650 N과 M (2) (Swift) (0) | 2023.03.20 |
| [BOJ] 백준 15649 N과 M (1) (Swift) (0) | 2023.03.20 |
