7287 : 재귀 프랙탈
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 5
•통과: 1
•만든사람: suakii
문제 설명
재귀(분할 정복)를 이용하여 직각 삼각형 형태의 시어핀스키(Sierpinski) 프랙탈 패턴을 출력하십시오.
재귀 깊이 $N$에서 격자의 세로 크기는 $2^N$ 줄이며, $i$번째 줄($0 \le i < 2^N$)에는 총 $i + 1$개의 문자가 위치합니다.
좌표 $(i, j)$ ($0 \le j \le i < 2^N$)에서 $j$가 $i$의 비트 부분집합일 때, 즉
[분할 정복 재귀 규칙]
- $N = 1$일 때 (기저 단계, $2^1 = 2$줄):
- 상단 $2^{k-1}$줄: $N = k-1$ 패턴을 그대로 1개 배치합니다.
- 하단 $2^{k-1}$줄: $N = k-1$ 패턴 2개를 좌우로 나란히 배치합니다. (사이의 빈 공간은 공백 처리)
※ 각 줄의 끝에 불필요한 오른쪽 공백(trailing spaces)은 제거하여 출력합니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
재귀 깊이 $N$에서 격자의 세로 크기는 $2^N$ 줄이며, $i$번째 줄($0 \le i < 2^N$)에는 총 $i + 1$개의 문자가 위치합니다.
좌표 $(i, j)$ ($0 \le j \le i < 2^N$)에서 $j$가 $i$의 비트 부분집합일 때, 즉
(i & j) == j인 경우 별표(*)를 출력하고, 그렇지 않은 경우 공백( )을 출력합니다.[분할 정복 재귀 규칙]
- $N = 1$일 때 (기저 단계, $2^1 = 2$줄):
*
**- 상단 $2^{k-1}$줄: $N = k-1$ 패턴을 그대로 1개 배치합니다.
- 하단 $2^{k-1}$줄: $N = k-1$ 패턴 2개를 좌우로 나란히 배치합니다. (사이의 빈 공간은 공백 처리)
※ 각 줄의 끝에 불필요한 오른쪽 공백(trailing spaces)은 제거하여 출력합니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 재귀 깊이 $N$이 주어집니다. ($1 \le N \le 6$)
출력 설명
시어핀스키 프랙탈 패턴을 $2^N$ 줄에 걸쳐 출력합니다.
(단, 각 줄 끝의 불필요한 오른쪽 공백은 제거합니다.)
(단, 각 줄 끝의 불필요한 오른쪽 공백은 제거합니다.)
입력 예시
COPY
복사되었습니다!
복사되었습니다!
2
출력 예시
COPY
복사되었습니다!
복사되었습니다!
*
**
* *
****도움
[예시 1: N = 1 (2줄)]
*
***
**
* *
*****
**
* *
****
* *
** **
* * * *
********# 비트 연산 방식
n = int(input())
size = 1 << n
for i in range(size):
row = "".join("*" if (i & j) == j else " " for j in range(i + 1))
print(row.rstrip())